Count Overlapping Rectangle Updates on a Grid
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Count Overlapping Rectangle Updates on a Grid
Implement `range_add_counts(n, rectangles)`.
Start with an `n x n` matrix of zeroes. Each rectangle is represented as `[row1, col1, row2, col2]` with inclusive, zero-based coordinates. For every rectangle, add one to each matrix cell inside that rectangle. Return the final matrix, where each cell therefore contains the number of input rectangles covering it.
## Example
For `n = 3` and `rectangles = [[0, 0, 1, 1], [1, 1, 2, 2]]`, return:
```text
[
[1, 1, 0],
[1, 2, 1],
[0, 1, 1]
]
```
## Constraints
- `1 <= n <= 500`
- `0 <= len(rectangles) <= 100_000`
- `0 <= row1 <= row2 < n`
- `0 <= col1 <= col2 < n`
Overview: Apply many inclusive rectangle increments to an n-by-n grid and return each cell's final coverage count. The constraints require handling up to one hundred thousand updates efficiently.
Read the full Google Software Engineer interview experience this question came from
Implement range_add_counts(n, rectangles). Begin with an n by n zero matrix. Each rectangle [row1, col1, row2, col2] uses inclusive zero-based coordinates and adds one to every covered cell. Return the final coverage-count matrix.
Constraints
- 1 <= n <= 500
- 0 <= len(rectangles) <= 100,000
- Every rectangle has valid inclusive coordinates within the grid.
- Rectangle updates may overlap or be identical.
Examples
Input: (1, [])
Expected Output: [[0]]
Explanation: No updates leave the only cell zero.
Input: (1, [[0, 0, 0, 0]])
Expected Output: [[1]]
Explanation: The one-cell rectangle covers the grid.
Hints
- Mark four corners in an (n + 1) by (n + 1) two-dimensional difference array.
- Recover cell counts with a two-dimensional prefix sum.
Community answers
Answer by czar
#include
class Solution {
public:
std::vector> range_add_counts(int n, const std::vector>& rectangles) {
std::vector> diff(n+1, std::vector(n+1, 0));
for (const auto &rect: rectangles) {
int r1 = rect[0], c1 = rect[1], r2 = rect[2], c2 = rect[3];
diff[r1][c1] += 1;
diff[r1][c2+1] -= 1;
diff[r2+1][c1] -= 1;
diff[r2+1][c2+1] += 1;
}
std::vector> result(n, std::vector(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i > 0) diff[i][j] += diff[i - 1][j];
if (j > 0) diff[i][j] += diff[i][j - 1];
if (i > 0 && j > 0) diff[i][j] -= diff[i - 1][j - 1];
result[i][j] = diff[i][j];
}
}
return result;
}
};
Answer by memo
def range_add_counts(n, queries):
ans = [[0] * n for _ in range(n)]
for x1, y1, x2, y2 in queries:
ans[x1][y1] += 1
if y2 + 1 < n: ans[x1][y2+1] -= 1
if x2 + 1 < n: ans[x2+1][y1] -= 1
if x2 + 1 < n and y2 + 1 < n: ans[x2+1][y2+1] += 1
for i in range(n):
for j in range(1, n):
ans[i][j] += ans[i][j-1]
for j in range(n):
for i in range(1, n):
ans[i][j] += ans[i-1][j]
return ans