0809HardBacktracking

Fewest Square Patches

Tracked in this browser only

Trains the technique from

LeetCode 1240Tiling a Rectangle with the Fewest Squares

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A glazier has to cover a rectangular panel that measures width units across and height units up, using square patches of glass.

Every patch has an integer side length of at least one unit and is laid with its sides parallel to the panel's sides. Patches may be of different sizes, they may not overlap each other, and no patch may stick out past the panel's edge. Together the patches must cover every point of the panel.

Return the smallest number of patches that covers the panel.

Examples

Example 1

Input: width = 4, height = 7
Output: 5

Five patches cover the panel: a 4 by 4 patch filling the bottom four rows, then a 3 by 3 patch in the left three columns of the remaining band, and three 1 by 1 patches stacked in the last column of that band.

Example 2

Input: width = 2, height = 5
Output: 4

Four patches cover the panel: two 2 by 2 patches filling the bottom four rows, then two 1 by 1 patches side by side in the top row.

Example 3

Input: width = 13, height = 13
Output: 1

The panel is already square, so one 13 by 13 patch covers it.

Constraints

1 <= width <= 13
1 <= height <= 13

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_square_patches(width: int, height: int) -> int:

Java

public int fewestSquarePatches(int width, int height)

The intended approach

Time Exponential in the worst case; with both prunes the whole 13 by 13 ceiling settles in well under a second.Space O(P) for the cache of column profiles reached, plus a recursion depth of at most width * height.

Lay patches from the bottom edge upwards, so the uncovered region is always described by one filled height per column. Repeatedly take the lowest column, and branch over every patch side that can sit there, widest first: the side cannot exceed the run of columns standing at that same height, nor the room left below the top edge. Two prunes keep the search small, abandoning a line once it has spent as many patches as the best complete cover found so far, and abandoning a column profile that has already been reached with no more patches than the current line has spent.

Pythonentry point: fewest_square_patches

def fewest_square_patches(width, height):
    # The uncovered part of the panel is always described by one height per
    # column, because patches are laid from the bottom edge upwards. Work on the
    # lowest column, and try every patch side that fits there, widest first: the
    # width is capped by the run of columns standing at the same height and the
    # side is capped by the room left under the top edge.
    #
    # Time: exponential in the worst case, cut down by two prunes -- abandon a
    # line once it has spent as many patches as the best cover already found,
    # and abandon a column profile already reached with no more patches.
    # Space: the profile cache, plus a recursion depth of at most width * height.
    cols, rows = width, height
    if cols > rows:
        cols, rows = rows, cols
    heights = [0] * cols
    best = [cols * rows]          # every unit square always works
    seen = {}

    def place(used):
        if used >= best[0]:
            return
        low = min(heights)
        if low == rows:
            best[0] = used
            return
        key = tuple(heights)
        prev = seen.get(key)
        if prev is not None and prev <= used:
            return
        seen[key] = used
        start = heights.index(low)
        run = 0
        while start + run < cols and heights[start + run] == low:
            run += 1
        cap = run if run < rows - low else rows - low
        for size in range(cap, 0, -1):
            for c in range(start, start + size):
                heights[c] += size
            place(used + 1)
            for c in range(start, start + size):
                heights[c] -= size

    place(0)
    return best[0]

The obvious version

Keep the set of covered cells as one bitmask per row, always work on the first uncovered cell in reading order, and try every patch that fits with its top-left corner there. It reasons about cells rather than column heights, so it also walks through partial covers that no bottom-up profile can express.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_square_patches(width, height):
    """Track the covered cells themselves, one bitmask per row of the panel.

    Always work on the first still-uncovered cell in reading order and try every
    patch that fits there with its top-left corner on that cell, largest first.
    Knows nothing about column heights, so it also explores shapes a
    bottom-up view cannot describe.
    """
    full = (1 << width) - 1
    best = [width * height]
    seen = {}

    def go(rows, used):
        if used >= best[0]:
            return
        spot = None
        for r in range(height):
            free = ~rows[r] & full
            if free:
                spot = (r, (free & -free).bit_length() - 1)
                break
        if spot is None:
            best[0] = used
            return
        key = tuple(rows)
        prev = seen.get(key)
        if prev is not None and prev <= used:
            return
        seen[key] = used
        r, c = spot
        size = 1
        while size <= height - r and size <= width - c:
            band = ((1 << size) - 1) << c
            if any(rows[r + k] & band for k in range(size)):
                break
            size += 1
        for s in range(size - 1, 0, -1):
            band = ((1 << s) - 1) << c
            for k in range(s):
                rows[r + k] |= band
            go(rows, used + 1)
            for k in range(s):
                rows[r + k] &= ~band

    go([0] * height, 0)
    return best[0]

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in