Scale Engineer

Stamping the Grid

Hard
#1942Time: `O(m * n * stampHeight * stampWidth)`. Both finding valid placements and checking coverage involve nested loops that depend on the stamp size, leading to this high complexity.Space: `O(m * n)` to store the `canStamp` grid which indicates possible stamp locations.1 company
Patterns
GreedyPrefix Sum
Data structures
ArrayMatrix
Companies
Rubrik

Prompt

You are given an m x n binary matrix grid where each cell is either 0 (empty) or 1 (occupied).

You are then given stamps of size stampHeight x stampWidth. We want to fit the stamps such that they follow the given restrictions and requirements:

  1. Cover all the empty cells.
  2. Do not cover any of the occupied cells.
  3. We can put as many stamps as we want.
  4. Stamps can overlap with each other.
  5. Stamps are not allowed to be rotated.
  6. Stamps must stay completely inside the grid.

Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.

 

Example 1:

Input: grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
Output: true
Explanation: We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.

Example 2:

Input: grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
Output: false 
Explanation: There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.

 

Constraints:

  • m == grid.length
  • n == grid[r].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 2 * 105
  • grid[r][c] is either 0 or 1.
  • 1 <= stampHeight, stampWidth <= 105

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but inefficient approach that directly simulates the process. It first identifies all valid stamp locations by exhaustively checking each potential stampHeight x stampWidth rectangle for occupied cells. Then, for each empty cell in the grid, it exhaustively checks if any of the valid stamp placements cover it. This method relies on nested loops and avoids complex data structures.

Algorithm

  • Create a boolean grid, canStamp, of size m x n.
  • Iterate through all possible top-left corners (r, c) for a stamp.
  • For each (r, c), scan the stampHeight x stampWidth area. If it contains no 1s, set canStamp[r][c] = true.
  • Iterate through every cell (i, j) of the original grid.
  • If grid[i][j] is 0, check if there exists a valid stamp placement (r', c') (where canStamp[r'][c'] is true) that covers (i, j).
  • If any empty cell (i, j) cannot be covered, return false.
  • If all empty cells are coverable, return true.

Walkthrough

This approach tackles the problem with nested loops, making it easy to understand but computationally expensive.

Algorithm

  1. Identify All Possible Stamp Placements (Slow Method):
    • Create a boolean grid, canStamp, of size m x n, to store whether a stamp's top-left corner can be placed at (r, c).
    • Iterate through every possible top-left corner (r, c) from (0, 0) to (m - stampHeight, n - stampWidth).
    • For each (r, c), perform a nested loop to scan the entire stampHeight x stampWidth area starting from (r, c).
    • If any cell (i, j) within this area has grid[i][j] == 1, then this placement is invalid.
    • If the scan completes without finding any 1s, mark canStamp[r][c] = true.
  2. Verify Coverage for Each Empty Cell (Slow Method):
    • Iterate through every cell (i, j) of the original grid.
    • If grid[i][j] == 0, we must check if it can be covered.
    • Initialize a boolean flag isCovered = false.
    • Iterate through all possible top-left corners (r', c') that could cover (i, j).
    • For each such (r', c'), check if canStamp[r'][c'] is true. If so, set isCovered = true and break.
    • If after checking all possibilities, isCovered is still false, return false.
  3. Final Result:
    • If the main loop completes, return true.

Code Snippet

class Solution {    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {        int m = grid.length;        int n = grid[0].length;         // Step 1: Identify all possible stamp placements (slowly)        boolean[][] canStamp = new boolean[m][n];        for (int r = 0; r <= m - stampHeight; r++) {            for (int c = 0; c <= n - stampWidth; c++) {                boolean possible = true;                for (int i = 0; i < stampHeight; i++) {                    for (int j = 0; j < stampWidth; j++) {                        if (grid[r + i][c + j] == 1) {                            possible = false;                            break;                        }                    }                    if (!possible) break;                }                if (possible) {                    canStamp[r][c] = true;                }            }        }         // Step 2: Verify coverage for each empty cell (slowly)        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 0) {                    boolean isCovered = false;                    // Check all stamps that could potentially cover (i, j)                    for (int r = Math.max(0, i - stampHeight + 1); r <= i; r++) {                        for (int c = Math.max(0, j - stampWidth + 1); c <= j; c++) {                            // Check if this potential stamp is within bounds and is valid                            if (r <= m - stampHeight && c <= n - stampWidth && canStamp[r][c]) {                                isCovered = true;                                break;                            }                        }                        if (isCovered) break;                    }                    if (!isCovered) {                        return false;                    }                }            }        }         return true;    }}

Complexity

Time

`O(m * n * stampHeight * stampWidth)`. Both finding valid placements and checking coverage involve nested loops that depend on the stamp size, leading to this high complexity.

Space

`O(m * n)` to store the `canStamp` grid which indicates possible stamp locations.

Trade-offs

Pros

  • The logic is direct and easy to follow, closely mirroring the problem's definition.

  • Requires minimal complex data structures, mainly just a boolean grid.

Cons

  • The time complexity is very high, making it impractical for the given constraints.

  • Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms.

Solutions

class Solution {public  boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {    int m = grid.length, n = grid[0].length;    int[][] s = new int[m + 1][n + 1];    for (int i = 1; i <= m; ++i) {      for (int j = 1; j <= n; ++j) {        s[i][j] =            s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];      }    }    int[][] d = new int[m + 2][n + 2];    for (int i = 1; i + stampHeight - 1 <= m; ++i) {      for (int j = 1; j + stampWidth - 1 <= n; ++j) {        int x = i + stampHeight - 1, y = j + stampWidth - 1;        if (s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0) {          d[i][j]++;          d[i][y + 1]--;          d[x + 1][j]--;          d[x + 1][y + 1]++;        }      }    }    for (int i = 1; i <= m; ++i) {      for (int j = 1; j <= n; ++j) {        d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];        if (grid[i - 1][j - 1] == 0 && d[i][j] == 0) {          return false;        }      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem