Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.
Example 1:
Input: n = 2, m = 3 Output: 3 Explanation:3squares are necessary to cover the rectangle.2(squares of1x1)1(square of2x2)
Example 2:
Input: n = 5, m = 8 Output: 5
Example 3:
Input: n = 11, m = 13 Output: 6
Constraints:
1 <= n, m <= 13Problem Overview: Given an n x m rectangle, you need to cover the entire area using the minimum number of integer-sized squares. Squares cannot overlap and must stay inside the rectangle. The challenge is choosing square placements so the total count of squares is minimized.
Approach 1: Dynamic Programming Approach (Time: O(n^2 * m^2), Space: O(n * m))
This approach builds a DP table where dp[a][b] represents the minimum number of squares required to tile an a x b rectangle. If a == b, the answer is 1 because the rectangle is already a square. Otherwise, split the rectangle horizontally or vertically and combine results from sub-rectangles. For every possible cut, compute dp[a][k] + dp[a][b-k] or dp[k][b] + dp[a-k][b] and take the minimum. The algorithm systematically explores rectangle partitions and reuses computed states, making it a classic dynamic programming solution.
Approach 2: Recursive Backtracking with Memoization (Time: exponential worst case, heavily pruned; Space: O(n * m))
This method simulates the tiling process directly. Track the current state of the rectangle (often as column heights or a filled grid). At each step, locate the first uncovered cell and attempt to place the largest possible square there. Recursively continue filling the remaining space. Memoization stores previously seen states to avoid recomputation, which dramatically reduces the search space. Pruning rules—such as abandoning paths that already exceed the current best solution—make the approach practical. The algorithm relies on backtracking combined with caching from recursion patterns.
Recommended for interviews: Recursive backtracking with memoization is the technique most interviewers expect. It demonstrates state exploration, pruning, and optimization through memoization. The DP formulation shows good understanding of rectangle partitioning, but the backtracking approach more directly models the tiling process and typically leads to the optimal solution faster in constrained inputs.
Use dynamic programming to solve the problem by maintaining a DP table where each entry dp[i][j] represents the minimum number of squares needed to tile a rectangle of size i x j. The base case is straightforward with small squares, and we build up from there by iterating through each rectangle size up to n x m.
This Python function defines a DP table where dp[i][j] gives the minimum number of tiles to tile a rectangle of size i x j. We iterate through rectangle sizes and fill this table based on smaller subproblems, considering potential square tiles within it.
Time Complexity: O(n^3 * m^3) due to triple nested iteration and considering every possible sub-problem size.
Space Complexity: O(n * m) for storing the DP table.
This approach leverages recursion coupled with memorization to try placing the largest possible square within a rectangle and then recursively solve the remainder. The memorization helps optimize by storing previously computed results for specific rectangle dimensions.
This Python function recursively tries all possible square positions and sizes, and stores intermediate results in a memo dictionary to avoid recalculation. This significantly reduces the redundant computation.
Python
Java
C#
JavaScript
Time Complexity: O(n^2 * m^2) due to recursive breakdown for subproblems within the range.
Space Complexity: O(n * m) due to memoization storage.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^3 * m^3) due to triple nested iteration and considering every possible sub-problem size. |
| Recursive Backtracking with Memorization | Time Complexity: O(n^2 * m^2) due to recursive breakdown for subproblems within the range. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Rectangle Splitting) | O(n^2 * m^2) | O(n * m) | When you want a deterministic DP formulation using rectangle partitioning |
| Recursive Backtracking with Memoization | Exponential worst case (heavily pruned) | O(n * m) | Best for interviews and constrained inputs where pruning drastically reduces search |
LeetCode 1240. Tiling a Rectangle with the Fewest Squares • Happy Coding • 8,320 views views
Watch 9 more video solutions →Practice Tiling a Rectangle with the Fewest Squares with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor