Apply several +1 rectangle updates to a matrix and return the final grid after all increments are accumulated.
Range Add Queries 2D
gfgYou are given an matrix initially filled with zeros and a list of update queries.
Each query is a rectangle described by its top-left and bottom-right coordinates. For every query, increment by $1$ every cell inside that submatrix, including the borders.
After processing all queries, return the final matrix.
A direct cell-by-cell simulation for every query may be too slow when the matrix and query count are large, so look for a way to accumulate the updates efficiently.
Input Format
- An integer matrix size .
- A list of rectangle updates, where each update is of the form
[r1, c1, r2, c2]. - Coordinates are 0-indexed and inclusive.
Output Format
- Return an matrix where each cell contains the total number of rectangle updates that cover it.
Constraints
- Each query satisfies and
- The number of queries may be large enough that an simulation is inefficient.
Example 1
Input
m = 3, n = 4, queries = [[0,0,1,1],[1,2,2,3]]
Output
[[1,1,0,0],[1,1,1,1],[0,0,1,1]]
Explanation
The first query increments the top-left 2x2 block. The second query increments the bottom-right 2x2 block. Overlapping cells would accumulate if any rectangles overlapped.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.