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.