Tiling a Rectangle with the Fewest Squares

Hard
1588.

Tiling a Rectangle with the Fewest Squares

Tiling a Rectangle with the Fewest Squares is a hard coding problem on backtracking and recursion, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var tilingRectangle = function(n, m) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

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

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

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

  1. Keep h[c], the filled height of each of the m columns, and best = n * m (all unit squares).
  2. dfs(count): if count >= best, return. Find the lowest height mn and its leftmost column i; if mn == n, the rectangle is full — set best = count.
  3. The square anchored at column i can be as wide as the run of columns at height mn starting at i, and no taller than n - mn.
  4. For each size from that maximum down to 1, raise those columns by the size, recurse with count + 1, and lower them back.
  5. 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