Stamping the Grid - Practice Coding Problems

Stamping the Grid - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 1, stampWidth = 3

› Output: true

💡 Note: We can place 1×3 stamps at positions (0,1), (1,1), and (2,1) to cover all empty cells without covering any occupied cells

Example 2 — Impossible Case

$ Input: grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0]], stampHeight = 2, stampWidth = 2

› Output: false

💡 Note: No 2×2 stamp can be placed without covering at least one occupied cell (1), so it's impossible to cover all empty cells

Example 3 — Small Stamp

$ Input: grid = [[1,0,0],[1,0,0],[1,0,0]], stampHeight = 1, stampWidth = 1

› Output: true

💡 Note: 1×1 stamps can be placed at all empty positions (0,1), (0,2), (1,1), (1,2), (2,1), (2,2) to cover everything

Constraints

m == grid.length
n == grid[r].length
1 ≤ m, n ≤ 10⁵
1 ≤ m × n ≤ 2 × 10⁵
grid[r][c] is either 0 or 1
1 ≤ stampHeight, stampWidth ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Binary matrix with occupied (1) and empty (0) cells

Stamp Placement

Place rectangular stamps to cover empty cells only

Coverage Check

Verify all empty cells are covered by at least one stamp

Key Takeaway

🎯 Key Insight: Check if every empty cell can be covered by at least one valid stamp placement

Asked in

G Google 15 f Meta 12

The key insight is that an empty cell can be covered if there exists at least one valid stamp position that includes it. The optimal approach uses prefix sums for O(1) rectangle queries to check stamp validity and difference arrays to efficiently track coverage. Time: O(mn), Space: O(mn)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(m²n²)	O(mn)	Try placing stamps at every position and simulate coverage
Prefix Sum Optimization	O(mn)	O(mn)	Use 2D prefix sums to efficiently check stamp validity and coverage

Brute Force Simulation — Algorithm Steps

Check each possible stamp position for validity
Mark all cells that can be covered by valid stamps
Verify all empty cells are covered

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Position

Test if stamp can be placed at current position

Mark Coverage

If valid, mark all cells this stamp would cover

Verify

Check if all empty cells are covered

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool canPlace(int** grid, int m, int n, int r, int c, int stampHeight, int stampWidth) {
    if (r + stampHeight > m || c + stampWidth > n) return false;
    for (int i = r; i < r + stampHeight; i++) {
        for (int j = c; j < c + stampWidth; j++) {
            if (grid[i][j] == 1) return false;
        }
    }
    return true;
}

bool solution(int** grid, int m, int n, int stampHeight, int stampWidth) {
    // Track which cells can be covered
    bool** covered = (bool**)malloc(m * sizeof(bool*));
    for (int i = 0; i < m; i++) {
        covered[i] = (bool*)calloc(n, sizeof(bool));
    }
    
    // Try placing stamp at each position
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (canPlace(grid, m, n, r, c, stampHeight, stampWidth)) {
                // Mark all cells covered by this stamp
                for (int i = r; i < r + stampHeight; i++) {
                    for (int j = c; j < c + stampWidth; j++) {
                        covered[i][j] = true;
                    }
                }
            }
        }
    }
    
    // Check if all empty cells are covered
    bool result = true;
    for (int i = 0; i < m && result; i++) {
        for (int j = 0; j < n && result; j++) {
            if (grid[i][j] == 0 && !covered[i][j]) {
                result = false;
            }
        }
    }
    
    // Clean up
    for (int i = 0; i < m; i++) {
        free(covered[i]);
    }
    free(covered);
    
    return result;
}

int main() {
    // For demo purposes, create a simple test case
    int m = 3, n = 3;
    int** grid = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Simple test grid [[1,0,0],[1,0,0],[1,0,0]]
    int testData[3][3] = {{1,0,0},{1,0,0},{1,0,0}};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            grid[i][j] = testData[i][j];
        }
    }
    
    int stampHeight = 1, stampWidth = 1;
    
    bool result = solution(grid, m, n, stampHeight, stampWidth);
    printf(result ? "true\n" : "false\n");
    
    // Clean up
    for (int i = 0; i < m; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

Nested loops check every position for every stamp placement

⚠ Quadratic Growth

Space Complexity

O(mn)

Coverage tracking matrix of same size as grid

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler