How hard is LeetCode 1240. Tiling a Rectangle with the Fewest Squares?

LeetCode 1240. Tiling a Rectangle with the Fewest Squares is rated Hard on LeetCode.

What topics does LeetCode 1240. Tiling a Rectangle with the Fewest Squares cover?

LeetCode 1240. Tiling a Rectangle with the Fewest Squares is tagged Backtracking on LeetCode.

Tiling a Rectangle with the Fewest Squares — LeetCode 1240 Python Solution

HardBacktracking

Problem: #1240
Pattern: Backtracking
Reading time: 6 min
Source: leetcode.com

The problem

Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.

Example

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.

Python solution

Python

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        def dfs(i: int, j: int, t: int):
            nonlocal ans
            if j == m:
                i += 1
                j = 0
            if i == n:
                ans = t
                return
            if filled[i] >> j & 1:
                dfs(i, j + 1, t)
            elif t + 1 < ans:
                r = c = 0
                for k in range(i, n):
                    if filled[k] >> j & 1:
                        break
                    r += 1
                for k in range(j, m):
                    if filled[i] >> k & 1:
                        break
                    c += 1
                mx = r if r < c else c
                for w in range(1, mx + 1):
                    for k in range(w):
                        filled[i + w - 1] |= 1 << (j + k)
                        filled[i + k] |= 1 << (j + w - 1)
                    dfs(i, j + w, t + 1)
                for x in range(i, i + mx):
                    for y in range(j, j + mx):
                        filled[x] ^= 1 << y

        ans = n * m
        filled = [0] * n
        dfs(0, 0, 0)
        return ans

Complexity

Measure	Complexity
Time	Exponential (worst case)
Space	O(depth) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1240. Tiling a Rectangle with the Fewest Squares is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1240. Tiling a Rectangle with the Fewest Squares?: LeetCode 1240. Tiling a Rectangle with the Fewest Squares is rated Hard on LeetCode.
What topics does LeetCode 1240. Tiling a Rectangle with the Fewest Squares cover?: LeetCode 1240. Tiling a Rectangle with the Fewest Squares is tagged Backtracking on LeetCode.