Increment Submatrices by One
Understanding the Problem
We start with an n x n grid of zeros. Each query gives us a rectangular region, and we need to add 1 to every cell inside that rectangle. After processing all queries, we return the final grid.
The direct interpretation is to loop through each rectangle and increment cells. The challenge is efficiency. With n up to 500, the matrix can have 250,000 cells, and with up to 10,000 queries, looping through every cell of every rectangle could touch up to 2.5 billion cells total. That is too slow.
This is a range update problem in two dimensions. In one dimension, range updates are solved efficiently with a difference array: mark the start and end of each update, then take a prefix sum. The same idea extends to 2D.
Key Constraints:
1 <= queries.length <= 10^4combined with1 <= n <= 500means a brute force of O(q n^2) reaches 2.5 10^9 operations, too slow within typical time limits. The approach has to make each query cheaper than scanning its full rectangle.0 <= row1i <= row2i < nand0 <= col1i <= col2i < nmeans queries are always valid rectangles. There is no need to validate or clamp boundaries.
Approach 1: Brute Force
Intuition
Do exactly what the problem says. For each query, iterate over every cell in the specified rectangle and add 1 to it, using a nested loop per query.
This is correct but slow. Each query can touch up to n^2 cells, and there are up to q queries, so the worst case is O(q * n^2). It serves as a baseline before optimizing.
Algorithm
- Create an
n x nmatrix initialized to all zeros. - For each query
[row1, col1, row2, col2]: - For every row
rfromrow1torow2: - For every column
cfromcol1tocol2: - Increment
mat[r][c]by 1. - Return the matrix.
Visualization and Code
Loading animation...
- Time Complexity: O(q n^2). Each query can update up to n^2 cells. With q queries, the total work is O(q n^2). For the given constraints, this is about 2.5 * 10^9, which is too slow.
- Space Complexity: O(n^2). We allocate the n x n output matrix. No additional space beyond the output.
The cost comes from touching every cell inside each rectangle. In 1D, a difference array marks a range update with two operations instead of visiting every element. The next approach applies that idea to each affected row.
Approach 2: Row-wise 1D Difference Array
Intuition
Process the matrix one row at a time. A query [row1, col1, row2, col2] affects row r only when row1 <= r <= row2, and when it does, it increments columns col1 through col2 in that row.
Incrementing a contiguous range of columns in a single row is a 1D range update, which a difference array handles efficiently. Instead of incrementing every element from col1 to col2, add 1 at position col1 and subtract 1 at position col2 + 1. After processing all queries for a row, one prefix sum pass recovers the actual values.
For each query, iterate over the affected rows and mark the column-range update in each row's difference array. This costs O(number of affected rows) per query, up to O(n), instead of O(n^2).
The prefix sum at position c equals the sum of all difference-array entries from 0 to c. A +1 at L adds to every prefix sum from L onward; the matching -1 at R+1 subtracts from every prefix sum from R+1 onward. The two cancel beyond R, so exactly positions L through R carry the increment. Multiple overlapping queries on the same row sum independently, so the final prefix sum is the total count of queries covering each position.
Algorithm
- Create an
n x nmatrixmatinitialized to zeros. Each row will serve as its own difference array. - For each query
[row1, col1, row2, col2]: - For every row
rfromrow1torow2: - Add 1 at
mat[r][col1]. - If
col2 + 1 < n, subtract 1 atmat[r][col2 + 1]. - For each row, compute the prefix sum to convert the difference array into actual values.
- Return the matrix.
Visualization and Code
Loading animation...
- Time Complexity: O(q n + n^2). For each query, we iterate over at most n rows doing O(1) work per row. The prefix sum pass is O(n^2). Total: O(q n + n^2).
- Space Complexity: O(n^2). We use the output matrix. No additional space beyond the output.
This applies the difference array to columns but still loops over every affected row. The next approach extends the difference array to both dimensions, marking the entire rectangle with four operations regardless of its size and recovering all values with a single 2D prefix sum pass.
Approach 3: 2D Difference Array (Optimal)
Intuition
The 1D difference array extends to two dimensions. Instead of marking each row individually, mark the entire rectangular update with four corner operations on a 2D difference array.
To add 1 to every cell in the rectangle from (r1, c1) to (r2, c2), we update a difference matrix diff at four points:
diff[r1][c1] += 1(start the increment here)diff[r1][c2 + 1] -= 1(cancel the increment past the right boundary)diff[r2 + 1][c1] -= 1(cancel the increment past the bottom boundary)diff[r2 + 1][c2 + 1] += 1(re-add because we subtracted twice at the bottom-right corner)
After marking all queries, we run a 2D prefix sum to recover the actual matrix values. Each query costs O(1) to mark, and the final prefix sum pass is O(n^2).
After the 2D prefix sum, the value at (r, c) equals the sum of all diff entries in the rectangle from (0, 0) to (r, c). A +1 at (r1, c1) therefore contributes to every cell at or below and to the right of it, covering the bottom-right quadrant anchored at (r1, c1). The -1 at (r1, c2+1) cancels that contribution in the quadrant past column c2. The -1 at (r2+1, c1) cancels it in the quadrant past row r2. Those two cancellation quadrants overlap in the region past both boundaries, where the increment has now been subtracted twice, so the +1 at (r2+1, c2+1) restores it once. What remains is exactly the rectangle from (r1, c1) to (r2, c2).
Algorithm
- Create an
(n + 1) x (n + 1)difference arraydiffinitialized to zeros (extra row and column to avoid boundary checks). - For each query
[row1, col1, row2, col2]: diff[row1][col1] += 1diff[row1][col2 + 1] -= 1diff[row2 + 1][col1] -= 1diff[row2 + 1][col2 + 1] += 1- Compute the 2D prefix sum over
diff: - First, do a row-wise prefix sum (left to right) for each row.
- Then, do a column-wise prefix sum (top to bottom) for each column.
- Extract the top-left
n x nportion as the result.
Visualization and Code
Loading animation...
- Time Complexity: O(q + n^2). Each query takes O(1) to mark four corners. The 2D prefix sum pass takes O(n^2). Total: O(q + n^2).
- Space Complexity: O(n^2). We allocate an (n+1) x (n+1) difference array and an n x n result matrix, both O(n^2).