1240. Tiling a Rectangle with the Fewest Squares


Problem Description

The problem is asking for the smallest number of integer-sided squares that can completely cover a rectangular area without any overlap or gaps. The dimensions of the rectangle are given by n (height) and m (width). Each square used must have its sides of integer length, and the task is to find the minimum number of such squares needed to cover the entire area of the rectangle.

Intuition

To find the minimum number of squares required to tile a given rectangle, a common approach is to use recursive backtracking, which is a kind of Depth First Search (DFS) algorithm. The basic idea is to place a square in the rectangle and then recursively attempt to fill the remaining area with smaller squares. The backtracking approach ensures that all possible combinations of squares are considered.

The intuition behind this solution is to start filling the rectangle with the largest possible square from the top-left corner and recursively move forward to fill in the uncovered area. Whenever we place a square, we update our filling state and then look for the next uncovered cell to continue the process. Each time we place a square, we increase our total count by one and try to minimize this count as we search for our solution. Whenever we hit a filled cell or the end of the rectangle, we return from the recursive call, as we've either found a complete tiling or reached a point where we can't place further squares.

The algorithm can be optimized by keeping track of the filled cells using a bit mask for each row, which allows for quick updates and checks. We also keep a global variable 'ans' that holds the minimum number of squares found so far, to avoid unnecessary recursive calls whenever we exceed this number.

This approach is efficient because it incorporates a few optimizations to prune the search space:

  1. If we reach the end of a row, we go to the beginning of the next row.
  2. If we reach the end of the rectangle, we've found a possible tiling and update the answer if it's better than the current one.
  3. We skip filled cells by moving to the next cell.
  4. Before placing a new square, we calculate the maximum possible size of the square that can be placed at the current position. This is done by checking the contiguous unfilled cells to the right and below the current cell.
  5. We place larger squares before smaller ones, aiming to reduce the number of squares required.
  6. While backtracking, we remove the placed squares from right to left and update the filled state accordingly.

In essence, we are exploring all feasible ways to tile the rectangle with squares, aiming to do so with the fewest squares possible, leveraging recursion to represent the depth of our search and backtracking to undo steps and explore different paths.

Learn more about Backtracking patterns.

Solution Approach

The provided code implements a solution approach using recursive backtracking. Here is a step-by-step explanation of the algorithm and how the solution works:

  1. A recursive depth-first search function dfs is defined within the tilingRectangle method. The dfs function accepts parameters i and j, which represent the current position (row and column) in the rectangle, and t, which is the current number of squares used to tile the rectangle so far.

  2. A global variable ans is used to keep track of the minimum number of squares discovered during the recursive exploration.

  3. The base cases of the dfs function are as follows:

    • If the current column j is equal to the rectangle width m, move to the start of the next row by incrementing i and resetting j to 0.
    • If the current row i is equal to the rectangle height n, which means the rectangle has been completely filled, update the global ans to the current tile count t.
  4. A bitmap filled is used to represent which cells in the rectangle are already covered by squares, where each integer in the filled list corresponds to a row in the rectangle. The bits of the integer indicate whether a specific column in that row is filled.

  5. The dfs function then checks if the current cell is already filled:

    • If it is filled, the function proceeds to the next cell by calling dfs(i, j + 1, t).
    • If it is not filled and the current tile count t + 1 is less than ans, the algorithm explores placing a new square in the current cell.
  6. To find the largest square that can be placed at the current position, the algorithm checks contiguous unfilled cells to the right and below the current cell to determine the possible size of the square. This size is stored in mx.

  7. The algorithm then places each possible square size starting from the largest (mx) down to the smallest (1). For each size w, it:

    • Marks the cells it covers as filled by updating the filled bitmap.
    • Calls dfs recursively for the next position with an updated tile count t + 1.
  8. After each recursive call, backtracking occurs. The algorithm unmarks the cells of the last square placed by updating the filled bitmap to remove the square of size w, allowing it to explore different configurations.

  9. Finally, after exploring all possibilities through dfs, the tilingRectangle method returns the global variable ans, which contains the minimum number of squares found to tile the rectangle.

The mentioned algorithm relies heavily on backtracking and bit manipulation to efficiently explore the search space and determine the optimal arrangement of squares. Despite the recursive nature and potentially large search space of the problem, these optimizations help manage the complexity and arrive at an answer within practical time constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's illustrate the solution approach using a small example where the dimensions of the rectangle are n = 2 (height) and m = 3 (width), and we are trying to find the smallest number of integer-sided squares that can cover this area.

  1. Start with no squares placed, so t = 0, i = 0, and j = 0. The filled bitmap is initially all zeros, indicating no cells are covered.

  2. Since we're at the top-left corner (cell 0,0), we want to place the largest square possible. Here, the largest square we can place is 2x2, because placing a 3x3 would exceed the rectangle's width.

  3. Place a 2x2 square which updates t to 1. The filled bitmap is updated to show that the first two rows and first two columns are covered.

    filled after placing 2x2 square:

    • Row 0: 110 (in binary)
    • Row 1: 110 (in binary)
  4. With the current cell (0,0) filled, we move to the first unfilled cell, which is (0,2).

  5. At position (0,2), the largest square we can place is a 1x1 because of the rectangle's edge. We update t to 2 and place the square.

    filled after placing 1x1 square:

    • Row 0: 111 (in binary)
    • Row 1: 110 (in binary)
  6. All cells in row 0 are now filled, so we move to the next row, position (1,2).

  7. Again, at position (1,2), the largest square we can place is 1x1. We update t to 3 and place the square.

    filled after placing another 1x1 square:

    • Row 0: 111 (in binary)
    • Row 1: 111 (in binary)
  8. The entire rectangle is now filled, and t = 3. Since this is the first solution found, ans is updated to 3.

  9. No further recursive calls are necessary as we have filled the entire rectangle, and we have updated the ans to the minimum number of squares.

  10. The algorithm ends, and we return ans, which is 3 for this example.

Thus, for a rectangle of size 2x3, the smallest number of integer-sided squares required to cover it without overlap or gaps is 3, consisting of one 2x2 square and two 1x1 squares.

Solution Implementation

1class Solution:
2    def tilingRectangle(self, n: int, m: int) -> int:
3      
4        # Define depth-first search function
5        def dfs(row: int, col: int, tiles_used: int):
6            nonlocal min_tiles  # Access the 'min_tiles' in the enclosing 'tilingRectangle' method
7            # Move to the next row if the end of the current row is reached
8            if col == m:
9                row += 1
10                col = 0
11            # Update the minimum number of tiles if the end of the rectangle is reached
12            if row == n:
13                min_tiles = tiles_used
14                return
15            # Continue with the next column if the current position is already filled
16            if filled[row] >> col & 1:
17                dfs(row, col + 1, tiles_used)
18            elif tiles_used + 1 < min_tiles:  # Only continue if it is possible to use fewer tiles than the current minimum
19                max_row, max_col = 0, 0
20                # Find how far we can extend the tile downwards  
21                for k in range(row, n):
22                    if filled[k] >> col & 1:
23                        break
24                    max_row += 1
25                # Find how far we can extend the tile to the right
26                for k in range(col, m):
27                    if filled[row] >> k & 1:
28                        break
29                    max_col += 1
30                # The maximum size of the square tile we can place
31                max_tile_size = min(max_row, max_col)
32
33                for x in range(row, row + max_tile_size):
34                    for y in range(col, col + max_tile_size):
35                        filled[x] |= 1 << y  # Mark the square as filled
36                # Attempt to place every possible square tile
37                for width in range(max_tile_size, 0, -1):
38                    dfs(row, col + width, tiles_used + 1)  # Recurse with one more tile
39                    # Undo the tile placement
40                    for k in range(width):
41                        filled[row + width - 1] ^= 1 << (col + k)
42                        if k < width - 1:
43                            filled[row + k] ^= 1 << (col + width - 1)
44
45        min_tiles = n * m  # Initialize the minimum number of tiles required with the maximum possible number
46        filled = [0] * n  # Represent each row with a bitmap to show if a cell is filled
47        dfs(0, 0, 0)  # Start the depth-first search from the top-left corner
48        return min_tiles  # Return the minimum number of tiles found
49
1class Solution {
2    private int numRows;         // Number of rows in the rectangle
3    private int numCols;         // Number of columns in the rectangle
4    private int[] tileCovered;   // Bit representation of tiles covered in each row
5    private int minTiles;        // Minimum number of tiles needed to cover the rectangle
6
7    public int tilingRectangle(int n, int m) {
8        numRows = n;
9        numCols = m;
10        minTiles = n * m;     // Initial maximum is the total area, which is the worst case
11        tileCovered = new int[n];
12        fillRectangle(0, 0, 0);
13        return minTiles;
14    }
15
16    private void fillRectangle(int row, int col, int tilesUsed) {
17        if (col == numCols) {
18            row++;        // Move to the next row
19            col = 0;      // Reset column to the first one
20        }
21        if (row == numRows) {
22            minTiles = tilesUsed;  // Update the minimum tiles used
23            return;
24        }
25        if ((tileCovered[row] >> col & 1) == 1) {
26            fillRectangle(row, col + 1, tilesUsed);  // If the tile at (row, col) is covered, move to next tile
27        } else if (tilesUsed + 1 < minTiles) {
28            int maxRow = 0, maxCol = 0;
29            // Calculate how far we can extend squares to the right and downwards
30            for (int i = row; i < numRows && (tileCovered[i] >> col & 1) == 0; ++i) {
31                maxRow++;
32            }
33            for (int j = col; j < numCols && (tileCovered[row] >> j & 1) == 0; ++j) {
34                maxCol++;
35            }
36            int maxSize = Math.min(maxRow, maxCol); // Maximum size of the square we can place
37          
38            // Mark the tiles as covered for the largest square initially
39            for (int x = row; x < row + maxSize; ++x) {
40                for (int y = col; y < col + maxSize; ++y) {
41                    tileCovered[x] |= 1 << y;
42                }
43            }
44
45            // Try placing squares of all possible sizes starting from largest to smallest
46            for (int squareSize = maxSize; squareSize > 0; --squareSize) {
47                fillRectangle(row, col + squareSize, tilesUsed + 1);
48              
49                // Uncover tiles for a square of the current size
50                for (int k = 0; k < squareSize; ++k) {
51                    tileCovered[row + squareSize - 1] ^= 1 << (col + k);
52                    if (k < squareSize - 1) {
53                        tileCovered[row + k] ^= 1 << (col + squareSize - 1);
54                    }
55                }
56            }
57        }
58    }
59}
60
1#include<cstring>
2
3class Solution {
4public:
5    int tilingRectangle(int n, int m) {
6        memset(isFilled, 0, sizeof(isFilled)); // Initialize all tiles as unfilled
7        this->height = n;
8        this->width = m;
9        minimumTiles = height * width; // Start with the worst-case: using all 1x1 tiles
10        dfs(0, 0, 0); // Begin the depth-first search at the top-left corner of the rectangle
11        return minimumTiles; // Return the minimal number of tiles that can fill the rectangle
12    }
13
14private:
15    int isFilled[13]; // Represents the filled status of each row up to 13, which is the maximum size
16    int height, width;
17    int minimumTiles;
18
19    void dfs(int row, int col, int tileCount) {
20        if (col == width) { // We've reached the end of a row
21            row++; // Move to the next row
22            col = 0; // Start from the first column of the new row
23        }
24        if (row == height) { // If every row is covered
25            minimumTiles = tileCount; // Update the minimum number of tiles
26            return;
27        }
28        if ((isFilled[row] >> col) & 1) { // If the current tile is already filled
29            dfs(row, col + 1, tileCount); // Move to the next column
30        } else if (tileCount + 1 < minimumTiles) { // If we could still potentially beat the current best
31            int maxRowExtent = 0, maxColExtent = 0;
32            for (int r = row; r < height; ++r) { // Calculate maximum extend in the rows
33                if ((isFilled[r] >> col) & 1)
34                    break;
35                maxRowExtent++;
36            }
37            for (int c = col; c < width; ++c) { // Calculate maximum extend in the columns
38                if ((isFilled[row] >> c) & 1)
39                    break;
40                maxColExtent++;
41            }
42
43            // Limit by the smaller dimension to identify the maximum size of square tile we can use
44            int maxSize = min(maxRowExtent, maxColExtent);
45
46            // Mark the filled tiles within the square defined by maxSize
47            for (int x = row; x < row + maxSize; ++x) {
48                for (int y = col; y < col + maxSize; ++y) {
49                    isFilled[x] |= 1 << y;
50                }
51            }
52
53            // Try to place a square tile and continue the search
54            for (int squareSize = maxSize; squareSize > 0; --squareSize) {
55                dfs(row, col + squareSize, tileCount + 1);
56              
57                // Unfill the tiles on the last row and column of the square to backtrack
58                for (int k = 0; k < squareSize; ++k) {
59                    isFilled[row + squareSize - 1] ^= 1 << (col + k);
60                    if (k < squareSize - 1) {
61                        isFilled[row + k] ^= 1 << (col + squareSize - 1);
62                    }
63                }
64            }
65        }
66    }
67};
68
1function tilingRectangle(n: number, m: number): number {
2    let minimumTiles = n * m; // Initialize the minimum number of tiles needed
3    const isFilled: number[] = new Array(n).fill(0); // Track filled cells in the rectangle
4
5    // Depth-first search to find the minimum number of tiles needed
6    const search = (row: number, col: number, tilesUsed: number) => {
7        // Move to the next row if the current one is filled
8        if (col === m) {
9            row++;
10            col = 0;
11        }
12        // Update the answer if we've filled the entire rectangle
13        if (row === n) {
14            minimumTiles = tilesUsed;
15            return;
16        }
17        // Skip already filled cells
18        if ((isFilled[row] >> col) & 1) {
19            search(row, col + 1, tilesUsed);
20            return;
21        }
22        // Only continue if we can potentially use fewer tiles than current minimumTiles
23        if (tilesUsed + 1 < minimumTiles) {
24            let maxRow = 0, maxCol = 0;
25            // Find the maximum size of the square we can place
26            for (let r = row; r < n; ++r) {
27                if ((isFilled[r] >> col) & 1) break;
28                maxRow++;
29            }
30            for (let c = col; c < m; ++c) {
31                if ((isFilled[row] >> c) & 1) break;
32                maxCol++;
33            }
34            const maxSize = Math.min(maxRow, maxCol); // Maximum tile size is limited by both dimensions
35
36            // Mark the cells as filled for the largest possible square
37            for (let x = row; x < row + maxSize; ++x) {
38                for (let y = col; y < col + maxSize; ++y) {
39                    isFilled[x] |= 1 << y;
40                }
41            }
42
43            // Try to find an optimum by trying all possible square sizes
44            for (let size = maxSize; size > 0; --size) {
45                search(row, col + size, tilesUsed + 1); // Recursively search with this square placed
46                // Unfill the cells used by the current square and decrement size
47                for (let k = 0; k < size; ++k) {
48                    isFilled[row + size - 1] ^= 1 << (col + k);
49                    if (k < size - 1) {
50                        isFilled[row + k] ^= 1 << (col + size - 1);
51                    }
52                }
53            }
54        }
55    };
56
57    search(0, 0, 0); // Start searching from the top-left cell with 0 tiles used
58    return minimumTiles; // Return the minimum number of tiles needed to fill the rectangle
59}
60
61// Example: 
62// console.log(tilingRectangle(2, 3)); // Output would be the minimum number of tiles needed.
63

Time and Space Complexity

The provided code is a backtracking algorithm to solve the problem of tiling a n x m rectangle with squares of different sizes. The algorithm performs a depth-first search (DFS) to find the smallest number of tiles required.

Time Complexity

The time complexity of the algorithm is hard to determine precisely due to the nature of the problem, but we can break down the complexity into different parts:

  1. DFS Calls: The DFS function is called recursively, attempting to fit squares of all possible sizes starting from the current largest possible (determined by mx variable). For each call to dfs, it is possible to place a square at the current position (i, j) and the range of squares is from 1x1 to mx x mx, where mx is the min possible size decided by the current state of filled array, i.e., smaller of the two sides from the current position to the edges of the unfilled region.

  2. Inner Loops: Within each call, there are two loops to determine how big a square can be placed at position (i, j). The time complexity for these loops, in the worst case, would be O(n) for the row check and O(m) for the column check, where n and m are the dimensions of the rectangle.

  3. Square Placement & Removal: Squares are placed and removed from the filled array using bitwise operations. These involve O(mx^2) operations for placement and O(w) operations for removal per depth.

Considering all the factors, the time complexity is exponential as it depends on the rectangle dimensions and the placement possibilities. The upper bound of this can be approximated as O(n * m * min(n, m)^(n * m)), but this is a very loose upper bound because the algorithm has several early stopping conditions (e.g., the check if t + 1 < ans) which can greatly reduce the search space.

Space Complexity

The space complexity is easier to ascertain:

  1. Recursion Stack: Since the algorithm uses DFS, the recursion stack height could go as deep as the total number of squares put into the rectangle. This is in the worst-case O(n * m).

  2. Filled Array: The state of the rectangle is maintained using an array filled that is O(n).

Thus, the space complexity is O(n * m) due to the recursion stack. The additional O(n) used by filled does not dominate the space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄