Stamping the grid

Array Greedy Matrix Prefix Sum

35.0% acceptance

Feb 25, 2026

418

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: Cover all the empty cells. Do not cover any of the occupied cells. We can put as many stamps as we want. Stamps can overlap with each other. Stamps are not allowed to be rotated. 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn possible_to_stamp(grid: Vec<Vec<i32>>, stamp_height: i32, stamp_width: i32) -> bool {
    let m = grid.len();
    let n = grid[0].len();
    let sh = stamp_height as usize;
    let sw = stamp_width as usize;

    // 2D prefix sum of grid to check if rectangle contains any occupied cell
    let mut gps = vec![vec![0i64; n + 1]; m + 1];
    for i in 0..m {
      for j in 0..n {
        gps[i + 1][j + 1] =
          grid[i][j] as i64 + gps[i][j + 1] + gps[i + 1][j] - gps[i][j];
      }
    }

    let grid_sum = |r1: usize, c1: usize, r2: usize, c2: usize| -> i64 {
      gps[r2][c2] - gps[r1][c2] - gps[r2][c1] + gps[r1][c1]
    };

    // can_stamp[i+1][j+1] = 1 if stamp can be placed with top-left at (i,j)
    let mut sps = vec![vec![0i64; n + 1]; m + 1];
    for i in 0..m {
      for j in 0..n {
        let r2 = i + sh;
        let c2 = j + sw;
        if r2 <= m && c2 <= n && grid_sum(i, j, r2, c2) == 0 {
          sps[i + 1][j + 1] = 1;
        }
      }
    }

    // Build prefix sum on sps
    for i in 0..m {
      for j in 0..n {
        sps[i + 1][j + 1] += sps[i][j + 1] + sps[i + 1][j] - sps[i][j];
      }
    }

    let stamp_sum = |r1: usize, c1: usize, r2: usize, c2: usize| -> i64 {
      // query from (r1,c1) to (r2,c2) exclusive in original coords -> inclusive in sps
      // top-left corner (r1, c1) inclusive to (r2-1, c2-1) inclusive in original
      // which is (r1+1, c1+1) to (r2, c2) in sps
      sps[r2][c2] - sps[r1][c2] - sps[r2][c1] + sps[r1][c1]
    };

    // Verify every empty cell is covered
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == 1 {
          continue;
        }
        // Cell (i,j) can be covered by stamp with TL in
        // row: [max(0, i-sh+1)..=i], col: [max(0, j-sw+1)..=j]
        let r1 = if i + 1 >= sh { i + 1 - sh } else { 0 };
        let c1 = if j + 1 >= sw { j + 1 - sw } else { 0 };
        let r2 = i + 1; // exclusive in sps means stamp top-left rows r1..i
        let c2 = j + 1;
        if stamp_sum(r1, c1, r2, c2) == 0 {
          return false;
        }
      }
    }
    true
  }
}