Problem statement

You are given an m × n binary matrix grid where 0 is an empty cell and 1 is occupied. You have unlimited stamps, each a rectangle of exactly stampHeight × stampWidth cells. Place stamps so that:

• every empty cell is covered by at least one stamp,
• no stamp covers an occupied cell,
• stamps may overlap each other,
• stamps may not be rotated, and must lie completely inside the grid.

Return true if the empty cells can be covered this way, and false otherwise.

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: Two overlapping 4 × 3 stamps — one on rows 0–3, one on rows 1–4, both on columns 1–3 — cover every empty cell.

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: The empty cell at the bottom-left corner (row 3, column 0) lies in no 2 × 2 block free of occupied cells.

Example 3

Input: grid = [[1,1],[1,1]], stampHeight = 3, stampWidth = 3
Output: true
Explanation: There is nothing to cover, so no stamp is needed.

Constraints

• m == grid.length
• n == grid[r].length
• 1 <= m, n <= 10^5
• 1 <= m * n <= 2 * 10^5
• grid[r][c] is 0 or 1
• 1 <= stampHeight, stampWidth <= 10^5

Hints for Stamping the Grid

1. Hint 1

   Since stamps may overlap, there is no harm in placing a stamp everywhere it is allowed. The question becomes: is every empty cell covered by some allowed placement?

2. Hint 2

   A placement with top-left corner (r, c) is allowed when its stampHeight × stampWidth rectangle fits in the grid and contains no 1. A 2D prefix sum over the grid answers "how many 1s in this rectangle?" in O(1).

3. Hint 3

   Mark every allowed placement in a 2D difference array (+1 at the corners pattern), take its 2D prefix sum to get each cell's cover count, and check that every empty cell has a positive count.

How to solve Stamping the Grid

Overlap is free, so stamp every legal position at once. Two 2D prefix-sum tricks make it linear: a prefix sum of the grid tests a placement in O(1), and a 2D difference array records every placement in O(1), after which another prefix sum gives each cell's coverage.

Approach

1. Build P, the 2D prefix sum of grid (size (m + 1) × (n + 1)).
2. For every top-left (r, c) with r + h <= m and c + w <= n, if the rectangle's sum from P is 0, add the placement to a difference array D: D[r][c] += 1, D[r][c + w] -= 1, D[r + h][c] -= 1, D[r + h][c + w] += 1.
3. Take the 2D prefix sum of D; the value at (i, j) is the number of placements covering that cell.
4. If any empty cell has coverage 0, return false; otherwise true.

Why it works

Every legal placement covers only empty cells, so using all of them violates nothing, and any valid stamping uses a subset of them — so a valid stamping exists iff the union of all legal placements covers every empty cell. The difference array adds 1 over exactly each placement's rectangle once prefix-summed, so the coverage counts are exact.

Complexity

• Time — O(m · n)
• Space — O(m · n)

Pitfalls

• Stamps larger than the grid have no legal placement at all — then the answer is true only if there are no empty cells.
• Use (m + 1) × (n + 1) (or + 2) arrays so the difference updates at r + h and c + w stay in bounds.
• Testing each placement cell by cell is O(m · n · h · w) — the prefix sum is what makes it fast.

Reference solution

Python

from typing import List

def possibleToStamp(grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
    m, n = len(grid), len(grid[0])
    h, w = stampHeight, stampWidth
    P = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        row, cur, nxt = grid[i], P[i], P[i + 1]
        for j in range(n):
            nxt[j + 1] = row[j] + cur[j + 1] + nxt[j] - cur[j]
    D = [[0] * (n + 2) for _ in range(m + 2)]
    for r in range(m - h + 1):
        for c in range(n - w + 1):
            if P[r + h][c + w] - P[r][c + w] - P[r + h][c] + P[r][c] == 0:
                D[r][c] += 1
                D[r][c + w] -= 1
                D[r + h][c] -= 1
                D[r + h][c + w] += 1
    cover = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            cover[i + 1][j + 1] = D[i][j] + cover[i][j + 1] + cover[i + 1][j] - cover[i][j]
            if grid[i][j] == 0 and cover[i + 1][j + 1] == 0:
                return False
    return True

Java

public static boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
    int m = grid.length, n = grid[0].length, h = stampHeight, w = stampWidth;
    int[][] P = new int[m + 1][n + 1];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            P[i + 1][j + 1] = grid[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j];
    int[][] D = new int[m + 2][n + 2];
    for (int r = 0; r + h <= m; r++)
        for (int c = 0; c + w <= n; c++)
            if (P[r + h][c + w] - P[r][c + w] - P[r + h][c] + P[r][c] == 0) {
                D[r][c]++; D[r][c + w]--; D[r + h][c]--; D[r + h][c + w]++;
            }
    int[][] C = new int[m + 1][n + 1];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            C[i + 1][j + 1] = D[i][j] + C[i][j + 1] + C[i + 1][j] - C[i][j];
            if (grid[i][j] == 0 && C[i + 1][j + 1] == 0) return false;
        }
    return true;
}

C++

bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
    int m = grid.size(), n = grid[0].size(), h = stampHeight, w = stampWidth;
    vector<vector<int>> P(m + 1, vector<int>(n + 1, 0)), D(m + 2, vector<int>(n + 2, 0)), C(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            P[i + 1][j + 1] = grid[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j];
    for (int r = 0; r + h <= m; r++)
        for (int c = 0; c + w <= n; c++)
            if (P[r + h][c + w] - P[r][c + w] - P[r + h][c] + P[r][c] == 0) {
                D[r][c]++; D[r][c + w]--; D[r + h][c]--; D[r + h][c + w]++;
            }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            C[i + 1][j + 1] = D[i][j] + C[i][j + 1] + C[i + 1][j] - C[i][j];
            if (grid[i][j] == 0 && C[i + 1][j + 1] == 0) return false;
        }
    return true;
}

JavaScript

var possibleToStamp = function(grid, stampHeight, stampWidth) {
    var m = grid.length, n = grid[0].length, h = stampHeight, w = stampWidth;
    var mat = function(r, c) { var a = []; for (var i = 0; i < r; i++) { var row = new Array(c); for (var j = 0; j < c; j++) row[j] = 0; a.push(row); } return a; };
    var P = mat(m + 1, n + 1);
    for (var i = 0; i < m; i++)
        for (var j = 0; j < n; j++)
            P[i + 1][j + 1] = grid[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j];
    var D = mat(m + 2, n + 2);
    for (var r = 0; r + h <= m; r++)
        for (var c = 0; c + w <= n; c++)
            if (P[r + h][c + w] - P[r][c + w] - P[r + h][c] + P[r][c] === 0) {
                D[r][c]++; D[r][c + w]--; D[r + h][c]--; D[r + h][c + w]++;
            }
    var C = mat(m + 1, n + 1);
    for (var x = 0; x < m; x++)
        for (var y = 0; y < n; y++) {
            C[x + 1][y + 1] = D[x][y] + C[x][y + 1] + C[x + 1][y] - C[x][y];
            if (grid[x][y] === 0 && C[x + 1][y + 1] === 0) return false;
        }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard
• Sum of Imbalance Numbers of All Subarrays Hard