#2132

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Stamping the Grid

Determine if a binary grid can be fully covered using fixed-size stamps by applying a greedy placement and validation strategy.

array greedy matrix prefix sum

Problem Statement

You are given an m x n binary matrix grid where 0 represents an empty cell and 1 represents an occupied cell. You also have a stamp of fixed size stampHeight x stampWidth. Your task is to determine if it is possible to cover all empty cells using one or more stamps without exceeding the grid boundaries or covering occupied cells.

Return true if it is possible to stamp all empty cells while following these restrictions; otherwise, return false. Each stamp must align with the grid cells, and stamps may overlap, but no stamp may cover a cell that is occupied. Optimize for the maximum coverage using a greedy placement approach validated with prefix sums.

Examples

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

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

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

Solution Approach

Compute Prefix Sums

Calculate a 2D prefix sum of the grid to quickly check if a submatrix of size stampHeight x stampWidth is free of occupied cells. This allows O(1) verification for each potential stamp position.

Greedy Stamp Placement

Iterate through the grid and place stamps at positions where they fully fit over empty cells. Always choose positions that cover the top-leftmost uncovered empty cell to maximize coverage early and maintain correctness.

Validate Full Coverage

After placing stamps, use the prefix sums to verify that every empty cell has been covered by at least one stamp. If any empty cell remains uncovered, return false; otherwise, return true.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) for building prefix sums and iterating possible stamp placements. Space complexity is O(m n) for the prefix sum matrix and auxiliary coverage arrays.

What Interviewers Usually Probe

Checks if you can combine greedy choices with fast submatrix checks using prefix sums.
Wants you to avoid O(m n stampHeight*stampWidth) naive checks for stamp placement.
Seeks a method to validate coverage efficiently after greedy placement.

Common Pitfalls or Variants

Common pitfalls

Attempting to check each stamp position by iterating over all cells inside the stamp, leading to timeouts.
Overlapping stamps incorrectly without verifying that all empty cells are eventually covered.
Ignoring boundary conditions where stamp placement would exceed grid dimensions.

Follow-up variants

Change the grid to allow rectangular stamps of varying dimensions and compute coverage feasibility.
Introduce obstacles that cannot be stamped and check if complete coverage of remaining empty cells is possible.
Count the minimum number of stamps required to cover all empty cells using a similar greedy plus validation approach.

FAQ

What is the best way to check if a stamp fits in 'Stamping the Grid'?

Use a 2D prefix sum to verify in O(1) time whether a submatrix of size stampHeight x stampWidth contains any occupied cells before placing a stamp.

Can stamps overlap in this problem?

Yes, stamps can overlap, but no stamp can cover a cell that is occupied.

Why is greedy placement necessary?

Greedy placement ensures that you cover empty cells early and reduce the risk of leaving uncovered zeros in unreachable positions.

What if the grid is very large?

Prefix sums allow efficient O(1) checks for stamp placement, preventing a brute-force O(m n stampHeight*stampWidth) time complexity that would be too slow.

How does GhostInterview help with the greedy plus invariant pattern?

It guides you to systematically place stamps and validate coverage using prefix sums, avoiding common mistakes and ensuring correctness efficiently.

terminal

Solution

Solution 1: Two-Dimensional Prefix Sum + Two-Dimensional Difference

According to the problem description, every empty cell must be covered by a stamp, and no occupied cell can be covered. Therefore, we can traverse the two-dimensional matrix, and for each cell, if all cells in the area of $stampHeight \times stampWidth$ with this cell as the upper left corner are empty (i.e., not occupied), then we can place a stamp at this cell.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def possibleToStamp(
        self, grid: List[List[int]], stampHeight: int, stampWidth: int
    ) -> bool:
        m, n = len(grid), len(grid[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(grid, 1):
            for j, v in enumerate(row, 1):
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v
        d = [[0] * (n + 2) for _ in range(m + 2)]
        for i in range(1, m - stampHeight + 2):
            for j in range(1, n - stampWidth + 2):
                x, y = i + stampHeight - 1, j + stampWidth - 1
                if s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0:
                    d[i][j] += 1
                    d[i][y + 1] -= 1
                    d[x + 1][j] -= 1
                    d[x + 1][y + 1] += 1
        for i, row in enumerate(grid, 1):
            for j, v in enumerate(row, 1):
                d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]
                if v == 0 and d[i][j] == 0:
                    return False
        return True

Continue Practicing

#2171 removing minimum number of magic beans #2234 maximum total beauty of the gardens #2245 maximum trailing zeros in a cornered path