Stamping the Grid Solution in Java

Links to Other Solutions

Problem Description

Ah, the classic “Stamping the Grid” problem! Imagine you’re a perfectionist artist who has a grid of canvas squares, and you want to stamp out all the empty squares (represented by 0s) with your fancy stamp. But wait! Your stamp has a specific height and width, and you can only place it on the grid if it perfectly covers a section of empty squares. If you find even one pesky 1 (representing a filled square) in the area where you want to stamp, your artistic dreams are dashed!

So, the challenge is to determine if you can cover all the empty squares with your stamp, without overlapping any filled squares. It’s like trying to cover a pizza with toppings, but you can’t let any of the toppings touch the crust!

Code Solution


class Solution {
  public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
    final int m = grid.length;
    final int n = grid[0].length;
    int[][] A = new int[m + 1][n + 1];
    int[][] B = new int[m + 1][n + 1];
    int[][] fit = new int[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + grid[i][j];
        if (i + 1 >= stampHeight && j + 1 >= stampWidth) {
          final int x = i - stampHeight + 1;
          final int y = j - stampWidth + 1;
          if (A[i + 1][j + 1] - A[x][j + 1] - A[i + 1][y] + A[x][y] == 0)
            fit[i][j] = 1;
        }
      }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + fit[i][j];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 0) {
          final int x = Math.min(i + stampHeight, m);
          final int y = Math.min(j + stampWidth, n);
          if (B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0)
            return false;
        }

    return true;
  }
}

Approach Explanation

The code uses a prefix sum technique to efficiently calculate the number of filled squares (1s) in any submatrix of the grid. It first builds a prefix sum array A to keep track of the number of 1s in the grid. Then, it checks for each position if a stamp can fit without overlapping any filled squares. If it can fit, it updates the fit array. Finally, it checks if all empty squares can be covered by verifying if there are any empty squares that cannot be stamped over.

Time and Space Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
Space Complexity: O(m * n) for the prefix sum arrays A and B.

Real-World Example

Think of this problem like trying to cover a messy floor with a rug. You want to cover all the bare spots (0s) with your rug (stamp), but if there’s a piece of furniture (1) in the way, you can’t just stamp over it! You need to find a way to maneuver your rug around the furniture to cover all the bare spots.