Stamping the Grid - Video Solutions

Problem Overview: You are given a binary m x n grid where 0 represents empty land and 1 represents blocked cells. You also have a stamp of fixed height and width. The task is to determine whether every empty cell can be covered by one or more stamps without covering any blocked cell. Stamps cannot rotate and must stay inside the grid.

Approach 1: Backtracking Search (Exponential Time)

This approach tries to place stamps recursively across the grid and checks whether all empty cells become covered. For each valid top‑left position, you attempt to place the stamp if all cells inside the rectangle are 0. The algorithm then marks the covered cells and recursively continues exploring the next placements. Because many placements overlap and branch heavily, the search space grows exponentially with grid size. Time complexity is roughly O((m*n) * branching^depth) in the worst case, and space complexity is O(m*n) for recursion state and coverage tracking. This approach demonstrates the brute‑force idea but quickly becomes impractical for large grids.

Approach 2: Greedy with Prefix Sum Optimization (O(m*n))

The optimal strategy avoids explicit placement simulation. Instead, it checks where stamps could be placed and verifies that every empty cell is covered by at least one valid stamp. First build a 2D prefix sum over the grid to query whether any rectangle contains blocked cells in constant time. For each position that could be the top‑left corner of a stamp, use the prefix sum to verify the rectangle is all zeros. If valid, mark the coverage using a 2D difference array so that large rectangular updates happen in constant time.

After processing all candidate positions, compute a prefix accumulation over the difference array to determine how many stamps cover each cell. Finally iterate through the grid: every 0 cell must have coverage greater than zero. If any empty cell remains uncovered, stamping the grid is impossible. This greedy validation works because stamps can overlap freely, so it is safe to mark every valid placement. Time complexity is O(m*n) and space complexity is O(m*n).

The key tools are fast rectangle queries with prefix sum and efficient range updates using a difference grid. The algorithm scans the matrix a constant number of times and greedily records every feasible stamp placement, which guarantees coverage checking without exploring combinations.

Recommended for interviews: The greedy + prefix sum approach is the expected solution. Interviewers want to see that you convert expensive rectangle checks into constant-time queries and avoid brute-force placement. Explaining the backtracking idea first shows you understand the constraints, while implementing the optimized solution demonstrates mastery of greedy reasoning and grid prefix sums.