LeetCode 2132 - Stamping the Grid

LeetCode Problem 2132

Difficulty: 🔴 Hard
Topics: Array, Greedy, Matrix, Prefix Sum

Solution

Problem Understanding

In this problem, we are given a binary matrix called grid. Every cell contains either:

• 0, meaning the cell is empty
• 1, meaning the cell is blocked or occupied

We are also given a rectangular stamp with dimensions:

• stampHeight
• stampWidth

The goal is to determine whether it is possible to place any number of these stamps onto the grid such that every empty cell is covered by at least one stamp.

The placement rules are very important:

• A stamp may only cover empty cells
• A stamp cannot overlap any occupied cell
• Stamps may overlap each other
• Stamps cannot rotate
• Every stamp must remain fully inside the grid

The problem only asks whether a valid arrangement exists. We do not need to return the actual placement of the stamps.

The main challenge comes from the constraints:

• m * n <= 2 * 10^5

This tells us the grid may be large in one dimension, so any algorithm worse than roughly linear or near-linear in the number of cells will likely time out.

A naive approach that checks every possible stamp against every empty cell repeatedly would become too expensive.

Several edge cases are important:

• The grid may already be fully occupied, in which case the answer is automatically true
• The stamp may be larger than the grid dimensions
• Some empty cells may be isolated so that no stamp can ever cover them
• Overlapping stamps are allowed, which changes the strategy significantly
• We only need coverage, not a minimal number of stamps

The key observation is that we do not need to simulate stamp placement greedily. Instead, we only need to determine whether every empty cell belongs to at least one valid stamp rectangle.

Approaches

Brute Force Approach

A straightforward approach is to try every possible top-left position for a stamp.

For each position:

1. Check whether the entire stamp rectangle stays inside the grid
2. Verify that every covered cell is empty
3. If valid, mark all cells in that rectangle as covered

After processing all placements, we scan the grid again and verify whether every empty cell was covered.

This approach is correct because it explicitly tests all legal stamp placements.

However, the performance is too slow.

Suppose:

• There are m * n possible positions
• Each stamp validation examines stampHeight * stampWidth cells

The complexity becomes:

$$O(m \times n \times stampHeight \times stampWidth)$$

This is far too large for the constraints.

Key Insight

The expensive part of the brute force approach is repeatedly checking whether a rectangle contains any occupied cells.

This immediately suggests using a 2D prefix sum.

With a prefix sum matrix, we can determine in constant time whether a rectangle contains any occupied cells.

Then we still face another issue:

• A single empty cell may be covered by many possible stamps
• Explicitly marking all covered cells for every stamp could still be expensive

To solve this efficiently, we use a second technique:

• A 2D difference array

Instead of updating every cell inside a stamp rectangle individually, we record rectangle updates in constant time. Later, we recover the final coverage counts using prefix sums.

This combination gives an efficient near-linear solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n × stampHeight × stampWidth)	O(m × n)	Explicitly checks every stamp area cell-by-cell
Optimal	O(m × n)	O(m × n)	Uses prefix sums and a 2D difference array

Algorithm Walkthrough

Step 1: Build a 2D Prefix Sum for Occupied Cells

We create a prefix sum matrix where:

$$prefix[r][c]$$

stores the number of occupied cells in the rectangle from (0,0) to (r-1,c-1).

This allows us to query any rectangle sum in constant time.

If a rectangle sum is zero, then the entire region is empty and a stamp may be placed there.

The rectangle query formula is:

$$sum = prefix[r2][c2] - prefix[r1][c2] - prefix[r2][c1] + prefix[r1][c1]$$

Step 2: Enumerate All Valid Stamp Placements

We iterate over every possible top-left corner (r,c).

The bottom-right corner becomes:

$$(r + stampHeight - 1,\ c + stampWidth - 1)$$

If this rectangle lies inside the grid and contains no occupied cells, then the stamp placement is valid.

Step 3: Record Coverage Using a Difference Array

Instead of directly marking every covered cell, we use a 2D difference matrix.

For a valid rectangle:

• add +1 at the top-left
• subtract 1 outside the rectangle boundaries

This lets us apply rectangle updates in constant time.

Specifically:

diff[r1][c1] += 1
diff[r2+1][c1] -= 1
diff[r1][c2+1] -= 1
diff[r2+1][c2+1] += 1

Step 4: Recover Final Coverage Counts

We compute the prefix sums of the difference matrix.

The resulting value at each cell tells us how many stamps cover that position.

Step 5: Verify Every Empty Cell is Covered

Finally, we scan the grid:

• If a cell is occupied, ignore it
• If a cell is empty but coverage count is zero, return false

If every empty cell is covered, return true.

Why it works

The algorithm works because it considers every possible valid stamp placement.

Any empty cell that can be covered by at least one legal stamp will receive positive coverage in the difference array reconstruction.

If an empty cell ends up uncovered, then no legal stamp placement could cover it, so the answer must be false.

The prefix sum guarantees constant-time rectangle validation, while the difference array guarantees constant-time rectangle updates. Together, they reduce the problem to linear complexity.

Python Solution

from typing import List

class Solution:
    def possibleToStamp(
        self,
        grid: List[List[int]],
        stampHeight: int,
        stampWidth: int
    ) -> bool:

        rows = len(grid)
        cols = len(grid[0])

        # Build prefix sum of occupied cells
        prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

        for r in range(rows):
            row_sum = 0
            for c in range(cols):
                row_sum += grid[r][c]
                prefix[r + 1][c + 1] = prefix[r][c + 1] + row_sum

        def rectangle_sum(r1: int, c1: int, r2: int, c2: int) -> int:
            return (
                prefix[r2 + 1][c2 + 1]
                - prefix[r1][c2 + 1]
                - prefix[r2 + 1][c1]
                + prefix[r1][c1]
            )

        # Difference array for coverage
        diff = [[0] * (cols + 1) for _ in range(rows + 1)]

        # Try every possible stamp placement
        for r in range(rows - stampHeight + 1):
            for c in range(cols - stampWidth + 1):

                r2 = r + stampHeight - 1
                c2 = c + stampWidth - 1

                # Entire rectangle must be empty
                if rectangle_sum(r, c, r2, c2) == 0:
                    diff[r][c] += 1
                    diff[r2 + 1][c] -= 1
                    diff[r][c2 + 1] -= 1
                    diff[r2 + 1][c2 + 1] += 1

        # Recover coverage counts
        coverage = [[0] * cols for _ in range(rows)]

        for r in range(rows):
            for c in range(cols):

                top = coverage[r - 1][c] if r > 0 else 0
                left = coverage[r][c - 1] if c > 0 else 0
                diagonal = coverage[r - 1][c - 1] if r > 0 and c > 0 else 0

                coverage[r][c] = (
                    diff[r][c]
                    + top
                    + left
                    - diagonal
                )

                # Empty cell must be covered
                if grid[r][c] == 0 and coverage[r][c] <= 0:
                    return False

        return True

The implementation begins by constructing a 2D prefix sum matrix. This allows the helper function rectangle_sum() to determine whether a stamp rectangle contains any occupied cells in constant time.

Next, the algorithm iterates through every possible stamp position. Whenever a fully empty rectangle is found, the rectangle is added into the difference array.

The difference array stores rectangle updates compactly. Instead of marking every covered cell individually, we only modify four boundary positions.

After all valid stamps are processed, the code reconstructs the final coverage matrix using prefix sums over the difference array.

During reconstruction, each empty cell is checked immediately. If any empty cell has zero coverage, the algorithm returns False.

Otherwise, every empty cell can be covered by at least one valid stamp placement, so the answer is True.

Go Solution

package main

func possibleToStamp(grid [][]int, stampHeight int, stampWidth int) bool {
	rows := len(grid)
	cols := len(grid[0])

	// Prefix sum of occupied cells
	prefix := make([][]int, rows+1)
	for i := range prefix {
		prefix[i] = make([]int, cols+1)
	}

	for r := 0; r < rows; r++ {
		rowSum := 0
		for c := 0; c < cols; c++ {
			rowSum += grid[r][c]
			prefix[r+1][c+1] = prefix[r][c+1] + rowSum
		}
	}

	rectSum := func(r1, c1, r2, c2 int) int {
		return prefix[r2+1][c2+1] -
			prefix[r1][c2+1] -
			prefix[r2+1][c1] +
			prefix[r1][c1]
	}

	// Difference array
	diff := make([][]int, rows+1)
	for i := range diff {
		diff[i] = make([]int, cols+1)
	}

	// Find valid stamp placements
	for r := 0; r <= rows-stampHeight; r++ {
		for c := 0; c <= cols-stampWidth; c++ {

			r2 := r + stampHeight - 1
			c2 := c + stampWidth - 1

			if rectSum(r, c, r2, c2) == 0 {
				diff[r][c]++
				diff[r2+1][c]--
				diff[r][c2+1]--
				diff[r2+1][c2+1]++
			}
		}
	}

	// Recover coverage counts
	coverage := make([][]int, rows)
	for i := range coverage {
		coverage[i] = make([]int, cols)
	}

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {

			top := 0
			left := 0
			diag := 0

			if r > 0 {
				top = coverage[r-1][c]
			}

			if c > 0 {
				left = coverage[r][c-1]
			}

			if r > 0 && c > 0 {
				diag = coverage[r-1][c-1]
			}

			coverage[r][c] = diff[r][c] + top + left - diag

			if grid[r][c] == 0 && coverage[r][c] <= 0 {
				return false
			}
		}
	}

	return true
}

The Go version follows the same algorithmic structure as the Python implementation.

The primary differences are:

• Go requires explicit allocation of all 2D slices
• Helper functions use closures
• Boundary conditions are handled manually because Go does not support negative indexing
• Integer overflow is not a concern because the maximum number of updates is bounded by m * n

Worked 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

Step 1: Valid Stamp Positions

Possible 4×3 rectangles:

Top Left	Valid?	Reason
(0,0)	No	Contains occupied cells in first column
(0,1)	Yes	Entire rectangle is empty
(1,0)	No	Contains occupied cells
(1,1)	Yes	Entire rectangle is empty

So two stamps are valid.

Step 2: Difference Array Updates

The valid stamps cover:

• rows [0..3], cols [1..3]
• rows [1..4], cols [1..3]

After reconstruction, every empty cell receives positive coverage.

Step 3: Final Coverage

Cell Type	Covered?
Occupied cells	Ignored
All empty cells	Yes

Result:

true

Example 2

Input:

grid =
[
  [1,0,0,0],
  [0,1,0,0],
  [0,0,1,0],
  [0,0,0,1]
]

stampHeight = 2
stampWidth = 2

Step 1: Check Every 2×2 Rectangle

Every possible 2×2 rectangle contains at least one occupied cell.

Therefore, no valid stamp placement exists.

Step 2: Coverage Reconstruction

Since no stamp was placed, every empty cell has coverage count 0.

The first uncovered empty cell causes the algorithm to return:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every cell is processed a constant number of times
Space	O(m × n)	Prefix sums, difference array, and coverage matrix

The prefix sum construction takes linear time.

The scan for valid stamp placements also takes linear time because every rectangle check is constant time.

Finally, reconstructing the coverage matrix is another linear pass.

No nested work proportional to stamp area occurs, which is why the solution remains efficient even for very large stamp dimensions.

Test Cases

from typing import List

class Solution:
    def possibleToStamp(
        self,
        grid: List[List[int]],
        stampHeight: int,
        stampWidth: int
    ) -> bool:

        rows = len(grid)
        cols = len(grid[0])

        prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

        for r in range(rows):
            row_sum = 0
            for c in range(cols):
                row_sum += grid[r][c]
                prefix[r + 1][c + 1] = prefix[r][c + 1] + row_sum

        def rectangle_sum(r1, c1, r2, c2):
            return (
                prefix[r2 + 1][c2 + 1]
                - prefix[r1][c2 + 1]
                - prefix[r2 + 1][c1]
                + prefix[r1][c1]
            )

        diff = [[0] * (cols + 1) for _ in range(rows + 1)]

        for r in range(rows - stampHeight + 1):
            for c in range(cols - stampWidth + 1):

                r2 = r + stampHeight - 1
                c2 = c + stampWidth - 1

                if rectangle_sum(r, c, r2, c2) == 0:
                    diff[r][c] += 1
                    diff[r2 + 1][c] -= 1
                    diff[r][c2 + 1] -= 1
                    diff[r2 + 1][c2 + 1] += 1

        coverage = [[0] * cols for _ in range(rows)]

        for r in range(rows):
            for c in range(cols):

                top = coverage[r - 1][c] if r > 0 else 0
                left = coverage[r][c - 1] if c > 0 else 0
                diag = coverage[r - 1][c - 1] if r > 0 and c > 0 else 0

                coverage[r][c] = diff[r][c] + top + left - diag

                if grid[r][c] == 0 and coverage[r][c] <= 0:
                    return False

        return True

sol = Solution()

assert sol.possibleToStamp(
    [[1,0,0,0],
     [1,0,0,0],
     [1,0,0,0],
     [1,0,0,0],
     [1,0,0,0]],
    4,
    3
) == True  # Provided example 1

assert sol.possibleToStamp(
    [[1,0,0,0],
     [0,1,0,0],
     [0,0,1,0],
     [0,0,0,1]],
    2,
    2
) == False  # Provided example 2

assert sol.possibleToStamp(
    [[0]],
    1,
    1
) == True  # Single empty cell

assert sol.possibleToStamp(
    [[1]],
    1,
    1
) == True  # Fully occupied grid

assert sol.possibleToStamp(
    [[0,0],
     [0,0]],
    3,
    3
) == False  # Stamp larger than grid

assert sol.possibleToStamp(
    [[0,0,0],
     [0,0,0]],
    1,
    1
) == True  # Every empty cell individually stampable

assert sol.possibleToStamp(
    [[0,1,0]],
    1,
    2
) == False  # Isolated empty cells

assert sol.possibleToStamp(
    [[0,0,0],
     [0,1,0],
     [0,0,0]],
    2,
    2
) == False  # Central obstacle blocks all 2x2 stamps

assert sol.possibleToStamp(
    [[0,0,0],
     [0,0,0],
     [0,0,0]],
    2,
    2
) == True  # Multiple overlapping stamps possible

Test Summary

Test	Why
Example 1	Verifies overlapping stamps work correctly
Example 2	Verifies impossible coverage detection
Single empty cell	Smallest valid empty grid
Single occupied cell	No stamping needed
Stamp larger than grid	Impossible placement dimensions
1×1 stamp	Simplest coverage case
Isolated empty cells	Empty cells may still be unreachable
Central obstacle	Internal blockage invalidates placements
Fully empty grid	Large overlapping coverage scenario

Edge Cases

Stamp Larger Than the Grid

If either stampHeight > rows or stampWidth > cols, then no stamp can ever be placed.

This is easy to mishandle because the placement loops may never execute. The implementation handles this naturally. If no valid placements exist, the coverage matrix remains zero everywhere. Any empty cell then immediately causes the algorithm to return False.

Fully Occupied Grid

A grid containing only 1s requires no stamps at all.

Some incorrect implementations attempt to force at least one stamp placement. Our implementation correctly ignores occupied cells during validation. Since there are no empty cells to check, the algorithm returns True.

Isolated Empty Cells

An empty cell may exist but still be impossible to cover because every potential stamp rectangle intersects an occupied cell or exceeds grid boundaries.

This is the most important logical edge case in the problem. The algorithm handles it by checking actual coverage counts after all valid stamp placements have been processed. If an empty cell never receives positive coverage, the answer is correctly False.

Overlapping Stamp Coverage

Multiple stamps may overlap heavily.

A greedy strategy that tries to avoid overlap can fail incorrectly. Our approach does not attempt constructive placement. Instead, it simply records every valid stamp rectangle. Since overlap is allowed, this guarantees no valid coverage opportunity is missed.