Tiling a Rectangle with the Fewest Squares — Solution
Tiling a Rectangle with the Fewest Squares solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Tiling a Rectangle with the Fewest Squares is a hard coding problem on backtracking and recursion, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Backtracking, Recursion
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Cover an n x m rectangle completely with squares whose sides are whole numbers. The squares may not overlap or stick out of the rectangle, and different squares may have different sizes.
Return the minimum number of squares needed.
Example 1
Input: n = 2, m = 3
Output: 3
Explanation: One 2x2 square and two 1x1 squares.
Example 2
Input: n = 5, m = 8
Output: 5
Explanation: A 5x5, a 3x3, a 2x2 and two 1x1 squares.
Example 3
Input: n = 11, m = 13
Output: 6
Explanation: The famous case where cutting the rectangle into two smaller rectangles is not optimal.
Constraints
1 <= n, m <= 13
Hints for Tiling a Rectangle with the Fewest Squares
Hint 1
Splitting the rectangle into two rectangles and recursing is tempting but wrong: 11 x 13 needs 6 squares, while the best sequence of straight cuts needs 8.
Hint 2
Search over actual placements instead. Keep the height filled so far in each column (a skyline); always fill the lowest, leftmost empty cell next — some square must cover it, with that cell as its top-left corner.
Hint 3
Try the largest square that fits there first, and prune any branch whose count already reaches the best answer found.
How to solve Tiling a Rectangle with the Fewest Squares
Every tiling can be built by repeatedly covering the lowest-leftmost uncovered cell with a square anchored there. Branch over the square's size, track the filled profile as column heights, and use branch-and-bound to cut the search.
Approach
- Keep
h[c], the filled height of each of themcolumns, andbest = n * m(all unit squares). dfs(count): ifcount >= best, return. Find the lowest heightmnand its leftmost columni; ifmn == n, the rectangle is full — setbest = count.- The square anchored at column
ican be as wide as the run of columns at heightmnstarting ati, and no taller thann - mn. - For each size from that maximum down to 1, raise those columns by the size, recurse with
count + 1, and lower them back. - Return
best.
Why it works
The lowest-leftmost uncovered cell must be the top-left corner of the square that covers it (anything to its left or below is already covered), so branching over that square's size enumerates every tiling. Trying big squares first finds a good tiling quickly, after which the count >= best bound discards almost everything else.
Complexity
- Time —
Exponential in the worst case; a few thousand nodes for every input with n, m ≤ 13 - Space —
O(m)
Pitfalls
- The "cut into two rectangles" DP is incorrect for 11 x 13 (it gives 8).
- The square anchored at the lowest cell is limited both by the run of equal-height columns and by the remaining height.
- n == m is a single square — handle it or let the search find it.
Reference solution
Python
def tilingRectangle(n: int, m: int) -> int:
h = [0] * m
best = [n * m]
def dfs(cnt):
if cnt >= best[0]:
return
mn = min(h)
if mn == n:
best[0] = cnt
return
i = h.index(mn)
j = i
while j < m and h[j] == mn and j - i < n - mn:
j += 1
for size in range(j - i, 0, -1):
for k in range(i, i + size):
h[k] += size
dfs(cnt + 1)
for k in range(i, i + size):
h[k] -= size
dfs(0)
return best[0]Java
static int tileBest;
public static int tilingRectangle(int n, int m) {
tileBest = n * m;
tileDfs(new int[m], n, m, 0);
return tileBest;
}
static void tileDfs(int[] h, int n, int m, int cnt) {
if (cnt >= tileBest) return;
int mn = n + 1, at = -1;
for (int c = 0; c < m; c++) if (h[c] < mn) { mn = h[c]; at = c; }
if (mn == n) { tileBest = cnt; return; }
int j = at;
while (j < m && h[j] == mn && j - at < n - mn) j++;
for (int size = j - at; size >= 1; size--) {
for (int k = at; k < at + size; k++) h[k] += size;
tileDfs(h, n, m, cnt + 1);
for (int k = at; k < at + size; k++) h[k] -= size;
}
}C++
void tileDfs(vector<int>& h, int n, int m, int cnt, int& best) {
if (cnt >= best) return;
int mn = n + 1, at = -1;
for (int c = 0; c < m; c++) if (h[c] < mn) { mn = h[c]; at = c; }
if (mn == n) { best = cnt; return; }
int j = at;
while (j < m && h[j] == mn && j - at < n - mn) j++;
for (int size = j - at; size >= 1; size--) {
for (int k = at; k < at + size; k++) h[k] += size;
tileDfs(h, n, m, cnt + 1, best);
for (int k = at; k < at + size; k++) h[k] -= size;
}
}
int tilingRectangle(int n, int m) {
vector<int> h(m, 0);
int best = n * m;
tileDfs(h, n, m, 0, best);
return best;
}JavaScript
var tilingRectangle = function(n, m) {
var h = new Array(m).fill(0);
var best = n * m;
var dfs = function(cnt) {
if (cnt >= best) return;
var mn = n + 1, at = -1;
for (var c = 0; c < m; c++) if (h[c] < mn) { mn = h[c]; at = c; }
if (mn === n) { best = cnt; return; }
var j = at;
while (j < m && h[j] === mn && j - at < n - mn) j++;
for (var size = j - at; size >= 1; size--) {
for (var k = at; k < at + size; k++) h[k] += size;
dfs(cnt + 1);
for (var k2 = at; k2 < at + size; k2++) h[k2] -= size;
}
};
dfs(0);
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 62 backtracking problems · the whole catalogue
Learn the technique: Backtracking · Recursion