2132. Stamping the Grid

Description

You are given an m x n binary matrix grid where each cell is either 0 (empty) or 1 (occupied).

You are then given stamps of size stampHeight x stampWidth. We want to fit the stamps such that they follow the given restrictions and requirements:

1. Cover all the empty cells.
2. Do not cover any of the occupied cells.
3. We can put as many stamps as we want.
4. Stamps can overlap with each other.
5. Stamps are not allowed to be rotated.
6. Stamps must stay completely inside the grid.

Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.

 

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
Explanation: 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 
Explanation: 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

 

Solutions

Solution: Prefix Sum

• Time complexity: O(mn)
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {number[][]} grid
 * @param {number} stampHeight
 * @param {number} stampWidth
 * @return {boolean}
 */
const possibleToStamp = function (grid, stampHeight, stampWidth) {
  const m = grid.length;
  const n = grid[0].length;
  const occupied = Array.from({ length: m }, () => new Array(n).fill(0));
  const fit = Array.from({ length: m }, () => new Array(n).fill(false));
  const fitCount = Array.from({ length: m }, () => new Array(n).fill(0));

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const value = grid[row][col];
      const upperOccupied = occupied[row - 1]?.[col] ?? 0;
      const leftOccupied = occupied[row][col - 1] ?? 0;
      const upperLeftOccupied = occupied[row - 1]?.[col - 1] ?? 0;

      occupied[row][col] = value + upperOccupied + leftOccupied - upperLeftOccupied;

      if (row + 1 < stampHeight || col + 1 < stampWidth) continue;

      const x = row - stampHeight;
      const y = col - stampWidth;
      const upperBoundary = occupied[x]?.[col] ?? 0;
      const leftBoundary = occupied[row][y] ?? 0;
      const upperLeftBoundary = occupied[x]?.[y] ?? 0;

      if (occupied[row][col] - upperBoundary - leftBoundary + upperLeftBoundary === 0) {
        fit[row][col] = true;
      }
    }
  }

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const value = fit[row][col] ? 1 : 0;
      const upperCount = fitCount[row - 1]?.[col] ?? 0;
      const leftCount = fitCount[row][col - 1] ?? 0;
      const upperLeftCount = fitCount[row - 1]?.[col - 1] ?? 0;

      fitCount[row][col] = value + upperCount + leftCount - upperLeftCount;
    }
  }

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      if (grid[row][col]) continue;

      const x = Math.min(row + stampHeight, m) - 1;
      const y = Math.min(col + stampWidth, n) - 1;
      const leftCount = fitCount[x][col - 1] ?? 0;
      const upperCount = fitCount[row - 1]?.[y] ?? 0;
      const upperLeftCount = fitCount[row - 1]?.[col - 1] ?? 0;

      if (fitCount[x][y] - upperCount - leftCount + upperLeftCount === 0) {
        return false;
      }
    }
  }

  return true;
};