first, build a prefix sum to quickly check if a stamp can be placed (area sum must be 0, meaning no obstacles). then use a 2d difference array to track which cells are covered by stamps.
after marking all possible stamp placements, accumulate the difference array to get actual coverage. every empty cell must be covered by at least one stamp.
steps
- build prefix sum for O(1) area queries
- mark all valid stamp positions in difference array
- accumulate difference array to get coverage
- verify all empty cells are covered
complexity
O(mn) time for building prefix, checking stamps, and verifying coverage. O(mn) space for the arrays. efficient grid processing.