Tiling a Rectangle with the Fewest Squares - Video Solutions

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.