1240. Tiling a Rectangle with the Fewest Squares Solution

Q: Is Tiling a Rectangle with the Fewest Squares easy or hard?

Tiling a Rectangle with the Fewest Squares is classified as a Hard problem. It requires advanced backtracking, careful pruning strategies, and efficient state representation to avoid exponential explosion. Many candidates struggle with designing the search state and optimization techniques.

Q: Tiling a Rectangle with the Fewest Squares Python/Java solution

Python and Java solutions usually implement recursive backtracking with memoization. The algorithm tracks filled cells, places the largest valid square, and recursively explores the next state. With pruning and caching, the solution handles rectangles up to 13 x 13 efficiently.

Q: How to solve Tiling a Rectangle with the Fewest Squares efficiently?

Use recursive backtracking that always selects the first uncovered cell and tries squares from largest to smallest. Maintain the grid state and recursively fill remaining regions. Add memoization for previously seen configurations and prune branches when the square count exceeds the current best. This strategy finds the optimal solution quickly for the problem constraints.

Q: What is the best approach for Tiling a Rectangle with the Fewest Squares?

Recursive backtracking with memoization is the most effective approach. The algorithm always fills the first empty cell and tries placing the largest possible square, recursively exploring the remaining space. Memoization stores previously visited states and pruning stops paths that exceed the current minimum. This dramatically reduces the exponential search space.

Q: Is Tiling a Rectangle with the Fewest Squares asked at Google/Amazon/Meta?

Rectangle tiling and backtracking optimization problems appear in interviews at companies like Google and Amazon because they test search pruning, recursion, and state representation. Variants of grid covering and minimum tiling are common in advanced algorithm interviews.

Q: What data structure is used in Tiling a Rectangle with the Fewest Squares?

Typical implementations use a 2D grid or a height profile array to represent the current filled state of the rectangle. Hash maps or dictionaries store memoized states for pruning repeated configurations. The algorithm heavily relies on recursion stacks for backtracking.

Q: What is the time complexity of Tiling a Rectangle with the Fewest Squares?

The backtracking solution has exponential worst‑case time complexity because it explores multiple square placement combinations. In practice, pruning and memoization reduce the search significantly for the constraint n, m ≤ 13. The dynamic programming rectangle-splitting approach runs in roughly O(n^2 * m^2) time with O(n * m) space.

The problem

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: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

Constraints:

1 <= n, m <= 13

Approach overview

Problem 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.

Approach 1: Dynamic Programming Approach

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.

Python

def tilingRectangle(n, m):
    dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if i == j:
                dp[i][j] = 1
            else:
                for k in range(1, i):
                    dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j])
                for k in range(1, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k])
                for k in range(1, min(i, j) + 1):
                    dp[i][j] = min(dp[i][j], dp[i - k][j] + dp[k][j - k] + 1)
    return dp[n][m]

Java

public class Solution {
    public int tilingRectangle(int n, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == j) {
                    dp[i][j] = 1;
                } else {
                    for (int k = 1; k < i; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[k][j] + dp[i - k][j]);
                    }
                    for (int k = 1; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[i][j - k]);
                    }
                    for (int k = 1; k <= Math.min(i, j); k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - k][j] + dp[k][j - k] + 1);
                    }
                }
            }
        }
        return dp[n][m];
    }
}

C++

#include <vector>
#include <algorithm>
#include <limits.h>

class Solution {
public:
    int tilingRectangle(int n, int m) {
        std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, INT_MAX));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (i == j) {
                    dp[i][j] = 1;
                } else {
                    for (int k = 1; k < i; ++k) {
                        dp[i][j] = std::min(dp[i][j], dp[k][j] + dp[i - k][j]);
                    }
                    for (int k = 1; k < j; ++k) {
                        dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[i][j - k]);
                    }
                    for (int k = 1; k <= std::min(i, j); ++k) {
                        dp[i][j] = std::min(dp[i][j], dp[i - k][j] + dp[k][j - k] + 1);
                    }
                }
            }
        }
        return dp[n][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.

Complexity

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.

Try this approach in the editor

Approach 2: Recursive Backtracking with Memorization

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.

Python

def tilingRectangle(n, m):
    def solve(x, y):
        if (x, y) in memo:
            return memo[(x, y)]
        if x == 0 or y == 0:
            return 0
        if x > y:
            x, y = y, x
        res = float('inf')
        for i in range(1, x + 1):
            res = min(res, solve(x - i, y) + solve(i, y - i) + 1)
        memo[(x, y)] = res
        return res
    memo = {}
    return solve(n, m)

Java

public class Solution {
    private int[][] memo;
    public int tilingRectangle(int n, int m) {
        memo = new int[n + 1][m + 1];
        return solve(n, m);
    }
    private int solve(int n, int m) {
        if (n == 0 || m == 0) return 0;
        if (memo[n][m] != 0) return memo[n][m]; 
        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= Math.min(n, m); i++) {
            res = Math.min(res, 1 + solve(n - i, m) + solve(i, m - i));
        }
        memo[n][m] = res;
        return res;
    }
}

JavaScript

const tilingRectangle = (n, m) => {
    const memo = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
    const solve = (x, y) => {
        if (x === 0 || y === 0) return 0;
        if (memo[x][y] !== 0) return memo[x][y];
        let res = Infinity;
        for (let i = 1; i <= Math.min(x, y); i++) {
            res = Math.min(res, 1 + solve(x - i, y) + solve(i, y - i));
        }
        memo[x][y] = res;
        return res;
    };
    return solve(n, m);
};

public class Solution {
    private int[,] memo;
    public int TilingRectangle(int n, int m) {
        memo = new int[n + 1, m + 1];
        return Solve(n, m);
    }
    private int Solve(int n, int m) {
        if (n == 0 || m == 0) return 0;
        if (memo[n, m] != 0) return memo[n, m];
        int res = int.MaxValue;
        for (int i = 1; i <= Math.Min(n, m); i++) {
            res = Math.Min(res, 1 + Solve(n - i, m) + Solve(i, m - i));
        }
        memo[n, m] = res;
        return res;
    }
}

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.

Complexity

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.

Try this approach in the editor

Approach 3: Recursive Backtracking + State Compression

We can perform recursive backtracking by position, during which we use a variable t to record the current number of tiles used.

If j = m, i.e., the i-th row has been completely filled, then we recurse to the next row, i.e., (i + 1, 0).
If i = n, it means that all positions have been filled, we update the answer and return.
If the current position (i, j) has been filled, then directly recurse to the next position (i, j + 1).
Otherwise, we enumerate the maximum square side length w that the current position (i, j) can fill, and fill all positions from (i, j) to (i + w - 1, j + w - 1), then recurse to the next position (i, j + w). When backtracking, we need to clear all positions from (i, j) to (i + w - 1, j + w - 1).

Since each position only has two states: filled or not filled, we can use an integer to represent the current state. We use an integer array filled of length n, where filled[i] represents the state of the i-th row. If the j-th bit of filled[i] is 1, it means that the i-th row and the j-th column have been filled, otherwise it means not filled.

TypeScript

function tilingRectangle(n: number, m: number): number {
    let ans = n * m;
    const filled: number[] = new Array(n).fill(0);
    const dfs = (i: number, j: number, t: number) => {
        if (j === m) {
            ++i;
            j = 0;
        }
        if (i === n) {
            ans = t;
            return;
        }
        if ((filled[i] >> j) & 1) {
            dfs(i, j + 1, t);
        } else if (t + 1 < ans) {
            let [r, c] = [0, 0];
            for (let k = i; k < n; ++k) {
                if ((filled[k] >> j) & 1) {
                    break;
                }
                ++r;
            }
            for (let k = j; k < m; ++k) {
                if ((filled[i] >> k) & 1) {
                    break;
                }
                ++c;
            }
            const mx = Math.min(r, c);
            for (let w = 1; w <= mx; ++w) {
                for (let k = 0; k < w; ++k) {
                    filled[i + w - 1] |= 1 << (j + k);
                    filled[i + k] |= 1 << (j + w - 1);
                }
                dfs(i, j + w, t + 1);
            }
            for (let x = i; x < i + mx; ++x) {
                for (let y = j; y < j + mx; ++y) {
                    filled[x] ^= 1 << y;
                }
            }
        }
    };
    dfs(0, 0, 0);
    return ans;
}

func tilingRectangle(n int, m int) int {
	ans := n * m
	filled := make([]int, n)
	var dfs func(i, j, t int)
	dfs = func(i, j, t int) {
		if j == m {
			i++
			j = 0
		}
		if i == n {
			ans = t
			return
		}
		if filled[i]>>j&1 == 1 {
			dfs(i, j+1, t)
		} else if t+1 < ans {
			var r, c int
			for k := i; k < n; k++ {
				if filled[k]>>j&1 == 1 {
					break
				}
				r++
			}
			for k := j; k < m; k++ {
				if filled[i]>>k&1 == 1 {
					break
				}
				c++
			}
			mx := min(r, c)
			for w := 1; w <= mx; w++ {
				for k := 0; k < w; k++ {
					filled[i+w-1] |= 1 << (j + k)
					filled[i+k] |= 1 << (j + w - 1)
				}
				dfs(i, j+w, t+1)
			}
			for x := i; x < i+mx; x++ {
				for y := j; y < j+mx; y++ {
					filled[x] ^= 1 << y
				}
			}
		}
	}
	dfs(0, 0, 0)
	return ans
}

Try this approach in the editor

Approach 4: Default Approach

TypeScript

function tilingRectangle(n: number, m: number): number {
    let ans = n * m;
    const filled: number[] = new Array(n).fill(0);
    const dfs = (i: number, j: number, t: number) => {
        if (j === m) {
            ++i;
            j = 0;
        }
        if (i === n) {
            ans = t;
            return;
        }
        if ((filled[i] >> j) & 1) {
            dfs(i, j + 1, t);
        } else if (t + 1 < ans) {
            let [r, c] = [0, 0];
            for (let k = i; k < n; ++k) {
                if ((filled[k] >> j) & 1) {
                    break;
                }
                ++r;
            }
            for (let k = j; k < m; ++k) {
                if ((filled[i] >> k) & 1) {
                    break;
                }
                ++c;
            }
            const mx = Math.min(r, c);
            for (let x = i; x < i + mx; ++x) {
                for (let y = j; y < j + mx; ++y) {
                    filled[x] |= 1 << y;
                }
            }
            for (let w = mx; w > 0; --w) {
                dfs(i, j + w, t + 1);
                for (let k = 0; k < w; ++k) {
                    filled[i + w - 1] ^= 1 << (j + k);
                    if (k < w - 1) {
                        filled[i + k] ^= 1 << (j + w - 1);
                    }
                }
            }
        }
    };
    dfs(0, 0, 0);
    return ans;
}

func tilingRectangle(n int, m int) int {
	ans := n * m
	filled := make([]int, n)
	var dfs func(i, j, t int)
	dfs = func(i, j, t int) {
		if j == m {
			i++
			j = 0
		}
		if i == n {
			ans = t
			return
		}
		if filled[i]>>j&1 == 1 {
			dfs(i, j+1, t)
		} else if t+1 < ans {
			var r, c int
			for k := i; k < n; k++ {
				if filled[k]>>j&1 == 1 {
					break
				}
				r++
			}
			for k := j; k < m; k++ {
				if filled[i]>>k&1 == 1 {
					break
				}
				c++
			}
			mx := min(r, c)
			for x := i; x < i+mx; x++ {
				for y := j; y < j+mx; y++ {
					filled[x] |= 1 << y
				}
			}
			for w := mx; w > 0; w-- {
				dfs(i, j+w, t+1)
				for k := 0; k < w; k++ {
					filled[i+w-1] ^= 1 << (j + k)
					if k < w-1 {
						filled[i+k] ^= 1 << (j + w - 1)
					}
				}
			}
		}
	}
	dfs(0, 0, 0)
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	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.
Recursive Backtracking with Memorization	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.
Recursive Backtracking + State Compression	–
Default Approach	–

Complexity analysis

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

Frequently asked questions

Is Tiling a Rectangle with the Fewest Squares easy or hard?

Tiling a Rectangle with the Fewest Squares is classified as a Hard problem. It requires advanced backtracking, careful pruning strategies, and efficient state representation to avoid exponential explosion. Many candidates struggle with designing the search state and optimization techniques.

Tiling a Rectangle with the Fewest Squares Python/Java solution

Python and Java solutions usually implement recursive backtracking with memoization. The algorithm tracks filled cells, places the largest valid square, and recursively explores the next state. With pruning and caching, the solution handles rectangles up to 13 x 13 efficiently.

How to solve Tiling a Rectangle with the Fewest Squares efficiently?

Use recursive backtracking that always selects the first uncovered cell and tries squares from largest to smallest. Maintain the grid state and recursively fill remaining regions. Add memoization for previously seen configurations and prune branches when the square count exceeds the current best. This strategy finds the optimal solution quickly for the problem constraints.

What is the best approach for Tiling a Rectangle with the Fewest Squares?

Recursive backtracking with memoization is the most effective approach. The algorithm always fills the first empty cell and tries placing the largest possible square, recursively exploring the remaining space. Memoization stores previously visited states and pruning stops paths that exceed the current minimum. This dramatically reduces the exponential search space.

Is Tiling a Rectangle with the Fewest Squares asked at Google/Amazon/Meta?

Rectangle tiling and backtracking optimization problems appear in interviews at companies like Google and Amazon because they test search pruning, recursion, and state representation. Variants of grid covering and minimum tiling are common in advanced algorithm interviews.

What data structure is used in Tiling a Rectangle with the Fewest Squares?

Typical implementations use a 2D grid or a height profile array to represent the current filled state of the rectangle. Hash maps or dictionaries store memoized states for pruning repeated configurations. The algorithm heavily relies on recursion stacks for backtracking.

What is the time complexity of Tiling a Rectangle with the Fewest Squares?

The backtracking solution has exponential worst‑case time complexity because it explores multiple square placement combinations. In practice, pruning and memoization reduce the search significantly for the constraint n, m ≤ 13. The dynamic programming rectangle-splitting approach runs in roughly O(n^2 * m^2) time with O(n * m) space.

Tiling a Rectangle with the Fewest Squares solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Recursive Backtracking with Memorization

Approach 3: Recursive Backtracking + State Compression

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Tiling a Rectangle with the Fewest Squares solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Recursive Backtracking with Memorization

Approach 3: Recursive Backtracking + State Compression

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems