2132. Stamping the Grid
Hard
50 Points
Array
Greedy
Matrix
Prefix Sum
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:
Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.
Examples
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 either 0 or 1.1 <= stampHeight, stampWidth <= 105
2132. Stamping the Grid
Hard
50 Points
Array
Greedy
Matrix
Prefix Sum
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:
Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.
Examples
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 either 0 or 1.1 <= stampHeight, stampWidth <= 105