Skip to main content
Talentd

Tiling a Rectangle with the Fewest Squares - Solution & Explanation

HardBacktracking22 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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.

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.

Code

PythonJavaC++

Python

Java

C++

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.

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.

Code

PythonJavaC#JavaScript

Python

Java

C#

JavaScript

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 MemoizationExponential worst case (heavily pruned)O(n * m)Best for interviews and constrained inputs where pruning drastically reduces search

Video Solution

LeetCode 1240. Tiling a Rectangle with the Fewest Squares • Happy Coding • 8,424 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Tiling a Rectangle with the Fewest Squares with our built-in code editor and test cases.

Practice on FleetCode
Previous

Selling Pieces of Wood