Count Rectangle Coverage on a Grid
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Count Rectangle Coverage on a Grid
You are given an `n x n` grid initially filled with zeroes and a list of inclusive rectangular updates. Each rectangle adds one to every covered cell.
Implement:
```text
range_add_counts(n, rectangles) -> list[list[int]]
```
Each rectangle is `[row1, col1, row2, col2]`, using zero-based inclusive coordinates. Return the final grid, where each cell contains the number of rectangles covering it.
### Example
```text
n = 3
rectangles = [
[0, 0, 1, 1],
[1, 1, 2, 2]
]
result = [
[1, 1, 0],
[1, 2, 1],
[0, 1, 1]
]
```
Cell `(1, 1)` is covered by both rectangles.
### Constraints
- `1 <= n <= 500`
- `0 <= len(rectangles) <= 100000`
- `0 <= row1 <= row2 < n`
- `0 <= col1 <= col2 < n`
- Duplicate rectangles count as separate updates.
- If `rectangles` is empty, return an all-zero grid.
### Clarifications
- Both lower and upper rectangle coordinates are included.
- The input list must not be mutated.
- Returning a newly allocated matrix is expected.
### Hints
- Updating every cell of every rectangle is too slow at the upper bound.
- A two-dimensional difference array can encode a rectangle with four boundary changes.
- Recover cell values by taking prefix sums across both dimensions, taking care at the grid edges.
### Discussion Extensions
- Derive the time and space complexity.
- How would you adapt the method if coordinates were very large but only a small number of points were queried?
- How would the boundary updates change for half-open rectangles?
Quick Answer: Apply many inclusive rectangular increments to a square grid and return the final coverage count for every cell. The exercise emphasizes upper-bound efficiency, duplicate updates, empty input, edge coordinates, non-mutating behavior, and a clear complexity analysis.
You are given an integer n describing an n x n grid that initially contains only zeroes, together with a list of rectangular updates. Each rectangle is given as [row1, col1, row2, col2] using zero-based, inclusive coordinates: it adds 1 to every cell (row, col) satisfying row1 <= row <= row2 and col1 <= col <= col2. Apply every update and return the finished n x n grid, where each cell holds the number of rectangles that cover it.
Duplicate rectangles in the list count as separate updates. If rectangles is empty, return an all-zero grid. The input list must not be mutated; return a newly allocated matrix.
Example 1:
n = 3, rectangles = [[0, 0, 1, 1], [1, 1, 2, 2]]
returns [[1, 1, 0], [1, 2, 1], [0, 1, 1]]
Cell (1, 1) is covered by both rectangles; every other covered cell is inside exactly one of them.
Example 2:
n = 2, rectangles = [[0, 0, 1, 1], [0, 0, 1, 1], [1, 1, 1, 1]]
returns [[2, 2], [2, 3]]
The duplicated full-grid rectangle contributes twice everywhere, and cell (1, 1) additionally receives the single-cell update.
Output semantics: return the complete grid as a list of n rows in row-major order (row 0 first), each row a list of n integers. Every cell count is at most len(rectangles) <= 100000, so all values fit in a 32-bit signed integer.
Constraints
- 1 <= n <= 500
- 0 <= len(rectangles) <= 100000
- 0 <= row1 <= row2 < n
- 0 <= col1 <= col2 < n
- Duplicate rectangles count as separate updates.
- If rectangles is empty, return an all-zero grid.
Examples
Input: (3, [[0, 0, 1, 1], [1, 1, 2, 2]])
Expected Output: [[1, 1, 0], [1, 2, 1], [0, 1, 1]]
Explanation: The worked example from the prompt: cell (1, 1) is covered by both rectangles.
Input: (3, [])
Expected Output: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
Explanation: No updates: the grid stays all zeroes.
Hints
- Updating every covered cell of every rectangle is too slow at the upper bound; look for a way to record one rectangle in O(1).
- A two-dimensional difference array can encode a whole rectangle with four boundary changes.
- Recover the final counts with prefix sums across both dimensions, taking care at the grid edges.