414. Target Rectangles
A satellite scans a field and reports a grid of integer readings: grid[r][c] is the reading of the cell in row r and column c. Positive values mean heat gain and negative values mean heat loss. An analyst is looking for rectangular patches, meaning blocks of cells that occupy a contiguous range of rows and a contiguous range of columns.
Given the integer target, count the non-empty rectangular patches of grid whose cell readings add up to exactly target. Patches with different corners are different even if their contents coincide. Return the number of such patches.
Example 1
- Input:
- grid = [[1,0,1],[0,1,0]], target = 2
- Output:
- 3
- Explanation:
The patches are the whole top row and the two 2x2 blocks (columns 0-1 and columns 1-2), so the answer is 3.
Example 2
- Input:
- grid = [[4,4],[4,4]], target = 3
- Output:
- 0
- Explanation:
Every patch sum is a multiple of 4, so none equals 3 and the answer is 0.
Constraints
- 1 ≤ grid.length, grid[0].length ≤ 300
- All rows have the same length
- -1000 ≤ grid[r][c] ≤ 1000
- -109 ≤ target ≤ 109
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(min(R,C)^2 * max(R,C))
- Space
- O(max(R,C))