We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Tiling a Rectangle with the Fewest Squares

Number: 1361

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a rectangle of dimensions n x m, the objective is to cover the entire area using the fewest number of integer-sided squares. The squares may be of different sizes, and they must completely tile the rectangle without overlapping.

Key Insights

  • Use recursive backtracking (DFS) to attempt placing a square at the first available empty position.
  • Always choose the largest square possible that fits into the remaining space to help reduce the number of tiles.
  • Prune paths that already exceed the best solution found so far.
  • Because the constraints are small (n, m <= 13), a brute-force DFS with smart ordering and pruning is sufficient.
  • Use a grid or bitmask to keep track of the covered area.

Space and Time Complexity

Time Complexity: Exponential in the worst-case, roughly O((nm)!) due to backtracking, but practical due to heavy pruning and small constraints. Space Complexity: O(nm) for the recursion call stack and grid state.

Solution

We solve the problem using a Depth-First Search (DFS) with backtracking. The algorithm iteratively finds the top-left most uncovered cell and attempts to place squares of all possible sizes that fit from that cell. For every square placement, the state of the grid is updated, and the DFS continues recursively to tile the remainder of the rectangle. If the current placement count exceeds the current best solution, the algorithm backtracks. This ensures we explore all possible tilings while pruning inefficient paths.

The main data structures used are:

  • A 2D list (grid) to represent the tiling state of the n x m rectangle.
  • Recursive stack that holds the current tiling state.
  • Variables that track the current count of squares and the minimum number found.

This approach leverages greedy placement combined with recursion. The trick is to always select the next empty cell in a fixed order (top-left priority) and try the largest square possible at that cell, which usually leads to fewer placements overall.

Code Solutions

# Python implementation for Tiling a Rectangle with the Fewest Squares

def tilingRectangle(n: int, m: int) -> int:
    # Initialize grid as n x m filled with zeros (0 = unfilled, 1 = filled)
    grid = [[0] * m for _ in range(n)]
    best = [float('inf')]  # use list for mutable integer in recursion

    def canPlace(x, y, size):
        # Check if square of length 'size' can be placed starting at (x, y)
        if x + size > n or y + size > m:
            return False
        for i in range(x, x + size):
            for j in range(y, y + size):
                if grid[i][j] == 1:
                    return False
        return True

    def placeSquare(x, y, size, val):
        # Mark/unmark cells covered by a square of size 'size' at (x, y)
        for i in range(x, x + size):
            for j in range(y, y + size):
                grid[i][j] = val

    def dfs(count):
        # Find the first uncovered cell (top-left)
        nonlocal best
        # Prune paths that already use more squares than current best
        if count >= best[0]:
            return

        found = False
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 0:
                    x, y = i, j
                    found = True
                    break
            if found:
                break

        # If no uncovered cells, have fully tiled the rectangle
        if not found:
            best[0] = min(best[0], count)
            return

        # Determine the maximum possible size for a square at (x, y)
        maxSize = min(n - x, m - y)
        for size in range(maxSize, 0, -1):
            if canPlace(x, y, size):
                # Place the square and explore further
                placeSquare(x, y, size, 1)
                dfs(count + 1)
                # Backtrack and remove the square
                placeSquare(x, y, size, 0)

    dfs(0)
    return best[0]

# Example usage:
print(tilingRectangle(2, 3))  # Expected output: 3
← Back to All Questions