Stamping the Grid
HardPrompt
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.
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.lengthn == grid[r].length1 <= m, n <= 1051 <= m * n <= 2 * 105grid[r][c]is either0or1.1 <= stampHeight, stampWidth <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward but inefficient approach that directly simulates the process. It first identifies all valid stamp locations by exhaustively checking each potential stampHeight x stampWidth rectangle for occupied cells. Then, for each empty cell in the grid, it exhaustively checks if any of the valid stamp placements cover it. This method relies on nested loops and avoids complex data structures.
Algorithm
- Create a boolean grid,
canStamp, of sizem x n. - Iterate through all possible top-left corners
(r, c)for a stamp. - For each
(r, c), scan thestampHeight x stampWidtharea. If it contains no1s, setcanStamp[r][c] = true. - Iterate through every cell
(i, j)of the originalgrid. - If
grid[i][j]is0, check if there exists a valid stamp placement(r', c')(wherecanStamp[r'][c']is true) that covers(i, j). - If any empty cell
(i, j)cannot be covered, returnfalse. - If all empty cells are coverable, return
true.
Walkthrough
This approach tackles the problem with nested loops, making it easy to understand but computationally expensive.
Algorithm
- Identify All Possible Stamp Placements (Slow Method):
- Create a boolean grid,
canStamp, of sizem x n, to store whether a stamp's top-left corner can be placed at(r, c). - Iterate through every possible top-left corner
(r, c)from(0, 0)to(m - stampHeight, n - stampWidth). - For each
(r, c), perform a nested loop to scan the entirestampHeight x stampWidtharea starting from(r, c). - If any cell
(i, j)within this area hasgrid[i][j] == 1, then this placement is invalid. - If the scan completes without finding any
1s, markcanStamp[r][c] = true.
- Create a boolean grid,
- Verify Coverage for Each Empty Cell (Slow Method):
- Iterate through every cell
(i, j)of the originalgrid. - If
grid[i][j] == 0, we must check if it can be covered. - Initialize a boolean flag
isCovered = false. - Iterate through all possible top-left corners
(r', c')that could cover(i, j). - For each such
(r', c'), check ifcanStamp[r'][c']istrue. If so, setisCovered = trueand break. - If after checking all possibilities,
isCoveredis stillfalse, returnfalse.
- Iterate through every cell
- Final Result:
- If the main loop completes, return
true.
- If the main loop completes, return
Code Snippet
class Solution { public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) { int m = grid.length; int n = grid[0].length; // Step 1: Identify all possible stamp placements (slowly) boolean[][] canStamp = new boolean[m][n]; for (int r = 0; r <= m - stampHeight; r++) { for (int c = 0; c <= n - stampWidth; c++) { boolean possible = true; for (int i = 0; i < stampHeight; i++) { for (int j = 0; j < stampWidth; j++) { if (grid[r + i][c + j] == 1) { possible = false; break; } } if (!possible) break; } if (possible) { canStamp[r][c] = true; } } } // Step 2: Verify coverage for each empty cell (slowly) for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0) { boolean isCovered = false; // Check all stamps that could potentially cover (i, j) for (int r = Math.max(0, i - stampHeight + 1); r <= i; r++) { for (int c = Math.max(0, j - stampWidth + 1); c <= j; c++) { // Check if this potential stamp is within bounds and is valid if (r <= m - stampHeight && c <= n - stampWidth && canStamp[r][c]) { isCovered = true; break; } } if (isCovered) break; } if (!isCovered) { return false; } } } } return true; }}Complexity
Time
`O(m * n * stampHeight * stampWidth)`. Both finding valid placements and checking coverage involve nested loops that depend on the stamp size, leading to this high complexity.
Space
`O(m * n)` to store the `canStamp` grid which indicates possible stamp locations.
Trade-offs
Pros
The logic is direct and easy to follow, closely mirroring the problem's definition.
Requires minimal complex data structures, mainly just a boolean grid.
Cons
The time complexity is very high, making it impractical for the given constraints.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms.
This optimal approach reframes the problem to efficiently handle rectangular queries and updates. It first uses a 2D prefix sum array to quickly find all valid stamp placements in O(m*n) time. Then, instead of checking coverage for each cell individually, it uses a 2D difference array (a sweep-line technique) to mark all covered regions simultaneously. By calculating a prefix sum on this difference array, we can determine which empty cells are covered, leading to an overall optimal solution.
Algorithm
- Create a 2D prefix sum array,
prefixOnes, to count1s in any rectangle inO(1). - Use
prefixOnesto identify all valid stamp placements (rectangles with zero1s) and store them in apossibleStampsgrid. This takesO(m*n). - Create a 2D difference array,
diff. - For each valid stamp placement at
(r, c), increment/decrement the four corners of the corresponding rectangle in thediffarray. - Compute a 2D prefix sum on the
diffarray to get a finalcoveredgrid.covered[i][j]will store the number of stamps covering cell(i, j). - Iterate through the grid. If
grid[i][j] == 0andcovered[i][j] == 0, returnfalse. - If the loop completes, return
true.
Walkthrough
This approach solves the problem efficiently by leveraging two powerful techniques for grid manipulation: 2D prefix sums and 2D difference arrays. The core idea is to work backward from the requirements.
Algorithm
- Calculate Prefix Sum of Occupied Cells:
- Create a 2D prefix sum array,
prefixOnes, of size(m+1) x (n+1).prefixOnes[i+1][j+1]will store the total count of1s in the rectangle from(0, 0)to(i, j). This allowsO(1)lookup for the number of1s in any sub-rectangle.
- Create a 2D prefix sum array,
- Identify All Possible Stamp Placements:
- Create a grid,
possibleStamps, of sizem x n. - Iterate through every possible top-left corner
(r, c). Use theprefixOnesarray to check if thestampHeight x stampWidthrectangle contains any1s. - If the rectangle is empty of
1s, mark it as a possible placement.
- Create a grid,
- Calculate Coverage using a 2D Difference Array:
- To find the union of all possible stamp areas efficiently, we use a 2D difference array
diff. - For each possible stamp placement at
(r, c), we update four points indiffto represent the addition of this rectangular area.
- To find the union of all possible stamp areas efficiently, we use a 2D difference array
- Reconstruct the Coverage Grid:
- By calculating the 2D prefix sum of the
diffarray, we obtain acoveredgrid wherecovered[i][j]equals the total number of valid stamps covering cell(i, j).
- By calculating the 2D prefix sum of the
- Final Verification:
- Iterate through the original
grid. If any cell(i, j)is empty (grid[i][j] == 0) but is not covered (covered[i][j] == 0), it's impossible to stamp the grid. Returnfalse. - If all empty cells are covered, return
true.
- Iterate through the original
Code Snippet
class Solution { public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) { int m = grid.length; int n = grid[0].length; // 1. Calculate prefix sum of occupied cells (1s) int[][] prefixOnes = new int[m + 1][n + 1]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { prefixOnes[i + 1][j + 1] = grid[i][j] + prefixOnes[i][j + 1] + prefixOnes[i + 1][j] - prefixOnes[i][j]; } } // 2. Identify all possible stamp placements int[][] possibleStamps = new int[m][n]; for (int r = 0; r <= m - stampHeight; r++) { for (int c = 0; c <= n - stampWidth; c++) { int r1 = r, c1 = c; int r2 = r + stampHeight - 1; int c2 = c + stampWidth - 1; int sum = prefixOnes[r2 + 1][c2 + 1] - prefixOnes[r1][c2 + 1] - prefixOnes[r2 + 1][c1] + prefixOnes[r1][c1]; if (sum == 0) { possibleStamps[r][c] = 1; } } } // 3. & 4. Use difference array to calculate coverage int[][] covered = new int[m + 1][n + 1]; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (possibleStamps[r][c] == 1) { int r_end = r + stampHeight; int c_end = c + stampWidth; covered[r][c]++; if (r_end < m + 1) covered[r_end][c]--; if (c_end < n + 1) covered[r][c_end]--; if (r_end < m + 1 && c_end < n + 1) covered[r_end][c_end]++; } } } // Compute prefix sum on the difference array for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i > 0) covered[i][j] += covered[i - 1][j]; if (j > 0) covered[i][j] += covered[i][j - 1]; if (i > 0 && j > 0) covered[i][j] -= covered[i - 1][j - 1]; } } // 5. Final verification for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0 && covered[i][j] == 0) { return false; } } } return true; }}Complexity
Time
`O(m * n)`. Each of the major steps—calculating prefix sums, finding possible stamps, applying the difference array, and final verification—takes linear time with respect to the number of cells in the grid.
Space
`O(m * n)`. Several auxiliary grids (`prefixOnes`, `possibleStamps`, `covered`) are needed, each with a size proportional to the input grid.
Trade-offs
Pros
Optimal time complexity, making it efficient enough for large grids.
Demonstrates a powerful and reusable pattern (prefix sums/difference arrays) for grid problems.
Cons
Requires more auxiliary space compared to the naive approach.
The logic, especially for the 2D difference array and prefix sums, can be complex to implement correctly.
Solutions
Solution
class Solution {public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) { int m = grid.length, n = grid[0].length; int[][] s = new int[m + 1][n + 1]; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1]; } } int[][] d = new int[m + 2][n + 2]; for (int i = 1; i + stampHeight - 1 <= m; ++i) { for (int j = 1; j + stampWidth - 1 <= n; ++j) { int x = i + stampHeight - 1, y = j + stampWidth - 1; if (s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0) { d[i][j]++; d[i][y + 1]--; d[x + 1][j]--; d[x + 1][y + 1]++; } } } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]; if (grid[i - 1][j - 1] == 0 && d[i][j] == 0) { return false; } } } return true; }}/** * @param {number[][]} grid * @param {number} stampHeight * @param {number} stampWidth * @return {boolean} */ var possibleToStamp = function (grid, stampHeight, stampWidth) { const m = grid.length; const n = grid[0].length; const s = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); for (let i = 1; i <= m; ++i) { for (let j = 1; j <= n; ++j) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1]; } } const d = Array.from({ length: m + 2 }, () => Array(n + 2).fill(0)); for (let i = 1; i + stampHeight - 1 <= m; ++i) { for (let j = 1; j + stampWidth - 1 <= n; ++j) { const [x, y] = [i + stampHeight - 1, j + stampWidth - 1]; if (s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] === 0) { d[i][j]++; d[i][y + 1]--; d[x + 1][j]--; d[x + 1][y + 1]++; } } } for (let i = 1; i <= m; ++i) { for (let j = 1; j <= n; ++j) { d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]; if (grid[i - 1][j - 1] === 0 && d[i][j] === 0) { return false; } } } return true; };class Solution {public: bool possibleToStamp(vector<vector<int>> &grid, int stampHeight, int stampWidth) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> s(m + 1, vector<int>(n + 1)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1]; } } vector<vector<int>> d(m + 2, vector<int>(n + 2)); for (int i = 1; i + stampHeight - 1 <= m; ++i) { for (int j = 1; j + stampWidth - 1 <= n; ++j) { int x = i + stampHeight - 1, y = j + stampWidth - 1; if (s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0) { d[i][j]++; d[i][y + 1]--; d[x + 1][j]--; d[x + 1][y + 1]++; } } } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]; if (grid[i - 1][j - 1] == 0 && d[i][j] == 0) { return false; } } } return true; }};class Solution: def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool: m, n = len(grid), len(grid[0]) s = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(grid, 1): for j, v in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v d = [[0] * (n + 2) for _ in range(m + 2)] for i in range(1, m - stampHeight + 2): for j in range(1, n - stampWidth + 2): x, y = i + stampHeight - 1, j + stampWidth - 1 if s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0: d[i][j] += 1 d[i][y + 1] -= 1 d[x + 1][j] -= 1 d[x + 1][y + 1] += 1 for i, row in enumerate(grid, 1): for j, v in enumerate(row, 1): d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] if v == 0 and d[i][j] == 0: return False return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.