LeetCode 1240 - Tiling a Rectangle with the Fewest Squares
The problem is asking us to completely cover a rectangle of size n x m with the fewest number of squares that have integer side lengths. The rectangle can be tiled with squares of any size, as long as each square fits entirely within the rectangle and there is no overlap.
Difficulty: 🔴 Hard
Topics: Backtracking
Solution
Problem Understanding
The problem is asking us to completely cover a rectangle of size n x m with the fewest number of squares that have integer side lengths. The rectangle can be tiled with squares of any size, as long as each square fits entirely within the rectangle and there is no overlap. The input consists of two integers, n and m, representing the height and width of the rectangle, respectively. The expected output is a single integer representing the minimum number of squares required to completely tile the rectangle.
The constraints, 1 <= n, m <= 13, indicate that the rectangle is relatively small, which suggests that a backtracking approach is feasible because the search space is limited, but careful pruning is needed to avoid exponential time blowup. Edge cases include rectangles that are already square (where the answer is 1), rectangles that are thin (e.g., 1xN), or rectangles where n and m share common factors versus those that are relatively prime, which affects the possible tiling configurations.
The problem guarantees that n and m are positive integers, so there is no need to handle zero or negative dimensions. However, small rectangles with prime dimensions can be particularly tricky because they often require a mix of smaller squares, increasing the search complexity.
Approaches
A brute-force approach would try all possible placements of squares at every available empty cell recursively. For each empty position, we could attempt squares of sizes from 1 up to the maximum square that fits in the remaining space. This method guarantees correctness because it explores every configuration, but it is extremely slow. The number of recursive calls grows combinatorially with the area of the rectangle, and for a 13x13 rectangle, it becomes computationally infeasible.
The key insight for an optimal approach is to use backtracking with pruning and heuristics. By always placing the largest possible square in the top-leftmost empty cell and keeping track of the current number of squares placed, we can prune any recursive paths that exceed the current best solution. Additionally, memoization of certain rectangle states or using a 2D board representation to track filled cells allows us to efficiently explore valid tilings. The small constraints make it feasible to perform a recursive depth-first search with pruning.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^(n*m)) | O(n*m) | Tries every square placement without pruning |
| Optimal | O(k^(n*m)) with pruning | O(n*m) | DFS/backtracking with largest-first heuristic and pruning |
Algorithm Walkthrough
- Initialize a 2D array or list representing the rectangle, marking all cells as empty.
- Define a recursive function that attempts to place squares starting from the top-leftmost empty cell.
- At each recursive step, find the first empty cell in row-major order.
- Determine the maximum square size that can fit starting at this cell without overlapping filled cells or exceeding rectangle boundaries.
- Iterate from the largest square size down to 1, placing a square and marking the corresponding cells as filled.
- Recurse with the updated rectangle state and an incremented count of squares used.
- Backtrack by removing the placed square and unmarking its cells.
- Track the minimum number of squares across all recursive paths.
- Return the minimum number of squares after exploring all valid tilings.
Why it works: The algorithm guarantees correctness because it explores every valid configuration, but efficiently prunes paths that cannot improve upon the best solution found so far. By always attempting the largest square first, it often reaches optimal solutions faster and avoids unnecessary exploration of smaller, suboptimal squares.
Python Solution
class Solution:
def tilingRectangle(self, n: int, m: int) -> int:
if n > m:
n, m = m, n
min_squares = n * m
board = [[0] * m for _ in range(n)]
def can_place(x, y, size):
if x + size > n or y + size > m:
return False
for i in range(x, x + size):
for j in range(y, y + size):
if board[i][j]:
return False
return True
def place_square(x, y, size, value):
for i in range(x, x + size):
for j in range(y, y + size):
board[i][j] = value
def dfs(count):
nonlocal min_squares
if count >= min_squares:
return
for i in range(n):
for j in range(m):
if board[i][j] == 0:
max_size = min(n - i, m - j)
for size in range(max_size, 0, -1):
if can_place(i, j, size):
place_square(i, j, size, 1)
dfs(count + 1)
place_square(i, j, size, 0)
return
min_squares = min(min_squares, count)
dfs(0)
return min_squares
The implementation first ensures n <= m to reduce symmetry. The can_place function checks if a square of a given size can fit at a position. place_square marks cells as filled or empty. The recursive dfs function explores all placements, pruning paths where the current count exceeds the best found so far. The algorithm always tries the largest square first for efficient pruning.
Go Solution
func tilingRectangle(n int, m int) int {
if n > m {
n, m = m, n
}
board := make([][]int, n)
for i := 0; i < n; i++ {
board[i] = make([]int, m)
}
minSquares := n * m
var canPlace func(x, y, size int) bool
canPlace = func(x, y, size int) bool {
if x+size > n || y+size > m {
return false
}
for i := x; i < x+size; i++ {
for j := y; j < y+size; j++ {
if board[i][j] == 1 {
return false
}
}
}
return true
}
var placeSquare func(x, y, size, val int)
placeSquare = func(x, y, size, val int) {
for i := x; i < x+size; i++ {
for j := y; j < y+size; j++ {
board[i][j] = val
}
}
}
var dfs func(count int)
dfs = func(count int) {
if count >= minSquares {
return
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if board[i][j] == 0 {
maxSize := min(n-i, m-j)
for size := maxSize; size >= 1; size-- {
if canPlace(i, j, size) {
placeSquare(i, j, size, 1)
dfs(count + 1)
placeSquare(i, j, size, 0)
}
}
return
}
}
}
if count < minSquares {
minSquares = count
}
}
dfs(0)
return minSquares
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
In Go, slices are used instead of lists, and functions like min are explicitly defined. Nil values are not a concern because we initialize a fully allocated board. Recursive functions use closures to capture board and minSquares.
Worked Examples
Example 1: n = 2, m = 3
- The board is initialized as a 2x3 grid.
- The top-left cell is empty, maximum square size is 2 (fits vertically and horizontally).
- Place 2x2 square in top-left, mark covered cells.
- Recurse, next empty cell is at (0,2), place 1x1 square.
- Next empty cell at (1,2), place 1x1 square.
- Board fully covered, total squares = 3.
Example 2: n = 5, m = 8
- Largest square at top-left is 5x5.
- Remaining rectangle is 5x3.
- Place 3x3 square in remaining rectangle.
- Remaining rectangle is 2x3, continue placing squares 2x2 and 1x1 as needed.
- Optimal tiling found using 5 squares.
Example 3: n = 11, m = 13
- Largest square at top-left is 11x11.
- Remaining 11x2 rectangle is tiled with 2x2 and 1x1 squares.
- Optimal solution requires 6 squares.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(k^(n*m)) with pruning | DFS explores configurations, pruning reduces number of paths significantly, k is average branching factor |
| Space | O(n*m) | The board array stores the current filled state of the rectangle |
The backtracking with pruning is feasible due to small constraints. The n*m <= 169 makes exhaustive search manageable when combined with heuristics.
Test Cases
# provided examples
assert