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`
Quick Answer: 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.
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.