We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stamping the Grid

Number: 2200

Difficulty: Hard

Paid? No

Companies: Rubrik

Problem Description

Given a binary matrix grid of dimensions m x n representing empty (0) and occupied (1) cells, and a stamp of fixed dimensions stampHeight x stampWidth, determine if it is possible to cover all the empty cells using as many stamps as needed subject to the following constraints:

  1. Stamps must cover only empty cells (cannot cover an occupied cell).
  2. Stamps may overlap with one another.
  3. Stamps cannot be rotated and must lie completely within the grid boundaries.

Return true if such a coverage is possible; otherwise, return false.

Key Insights

  • Precompute a 2D prefix sum for the grid to efficiently check if a submatrix (that would be covered by a stamp) contains any occupied cells.
  • For every possible stamp placement (i.e. every potential top‐left coordinate fitting the stamp inside the grid), mark it as valid if the submatrix (of size stampHeight x stampWidth) is fully empty.
  • Use a 2D difference (or imos) technique to record the influence (coverage) of each valid stamp placement over the grid.
  • After accumulating the differences to get the total coverage for each grid cell, verify that every empty cell is covered by at least one stamp placement.
  • The challenge lies in efficiently marking and checking candidate stamp placements while keeping within the problem constraints.

Space and Time Complexity

Time Complexity: O(mn) because we process each grid cell a constant number of times (prefix sum computation, checking valid placements, and applying the 2D difference technique). Space Complexity: O(mn) for storing the prefix sum array and the difference array.

Solution

We solve the problem in several steps:

  1. Create a 2D prefix sum array over grid to quickly compute the sum within any rectangular submatrix.
  2. For every possible position where a stamp could be placed (top-left coordinate such that the stamp fits inside the grid), use the prefix sum to check if the corresponding submatrix is completely empty. If yes, mark that cell in a valid-placement matrix.
  3. Use a 2D difference array (also known as the imos method) to simulate the effect of each valid stamp placement. For a valid placement starting at (i, j), add +1 at (i, j) and perform appropriate subtractions at (i + stampHeight, j) and (i, j + stampWidth) and an addition at (i + stampHeight, j + stampWidth) such that when we take cumulative sums, every cell in the stamping area is incremented.
  4. Compute the accumulated coverage grid from the difference array.
  5. Finally, iterate over every cell in the grid. If the cell is empty (0) and the accumulated coverage is less than 1 (i.e. it is not covered by any stamp), return false. Otherwise, return true.

Tricks/Gotchas:

  • Ensure that indices used for the stamp placements and the difference array adjustments do not go out of bounds.
  • The coverage verification step must consider that stamps may overlap and ensure that each empty cell can be reached by at least one valid stamp area.

Code Solutions

# Python solution with detailed comments
class Solution:
    def possibleToStamp(self, grid, stampHeight, stampWidth):
        m, n = len(grid), len(grid[0])
        
        # Step 1: Build a 2D prefix sum of grid for occupied cells.
        pref = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                pref[i+1][j+1] = grid[i][j] + pref[i][j+1] + pref[i+1][j] - pref[i][j]
                
        # Helper function to get sum of submatrix from (r1, c1) to (r2, c2) inclusive.
        def get_sum(r1, c1, r2, c2):
            return pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1]
        
        # Step 2: Construct valid stamp placement matrix.
        valid = [[0] * n for _ in range(m)]
        for i in range(m - stampHeight + 1):
            for j in range(n - stampWidth + 1):
                # Check if the area from (i, j) to (i+stampHeight-1, j+stampWidth-1) is empty.
                if get_sum(i, j, i + stampHeight - 1, j + stampWidth - 1) == 0:
                    valid[i][j] = 1
        
        # Step 3: Use 2D difference array for valid stamp placements.
        diff = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m - stampHeight + 1):
            for j in range(n - stampWidth + 1):
                if valid[i][j]:
                    # Mark the difference array for this valid placement.
                    diff[i][j] += 1
                    diff[i + stampHeight][j] -= 1
                    diff[i][j + stampWidth] -= 1
                    diff[i + stampHeight][j + stampWidth] += 1
        
        # Step 4: Accumulate the diff array to compute coverage.
        # First accumulate rows.
        for i in range(m):
            for j in range(1, n):
                diff[i][j] += diff[i][j-1]
        # Then accumulate columns.
        for j in range(n):
            for i in range(1, m):
                diff[i][j] += diff[i-1][j]
        
        # Step 5: Check that all empty cells in grid are covered by at least one stamp.
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and diff[i][j] <= 0:
                    return False
        return True

# Example usage:
# sol = Solution()
# print(sol.possibleToStamp([[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], 4, 3))
← Back to All Questions