You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes.
You are also given a 2D integer array query. For each query[i] = [row1i, col1i, row2i, col2i], you should do the following operation:
1 to every element in the submatrix with the top left corner (row1i, col1i) and the bottom right corner (row2i, col2i). That is, add 1 to mat[x][y] for all row1i <= x <= row2i and col1i <= y <= col2i.Return the matrix mat after performing every query.
Example 1:
Input: n = 3, queries = [[1,1,2,2],[0,0,1,1]] Output: [[1,1,0],[1,2,1],[0,1,1]] Explanation: The diagram above shows the initial matrix, the matrix after the first query, and the matrix after the second query. - In the first query, we add 1 to every element in the submatrix with the top left corner (1, 1) and bottom right corner (2, 2). - In the second query, we add 1 to every element in the submatrix with the top left corner (0, 0) and bottom right corner (1, 1).
Example 2:
Input: n = 2, queries = [[0,0,1,1]] Output: [[1,1],[1,1]] Explanation: The diagram above shows the initial matrix and the matrix after the first query. - In the first query we add 1 to every element in the matrix.
Constraints:
1 <= n <= 5001 <= queries.length <= 1040 <= row1i <= row2i < n0 <= col1i <= col2i < nThe key challenge in #2536 Increment Submatrices by One is efficiently applying multiple increment operations over rectangular regions of a matrix. A naive approach would update every cell inside each query range, which leads to O(q * n * n) time in the worst case and quickly becomes inefficient for large inputs.
A more optimal strategy uses a 2D difference array (prefix sum technique). Instead of updating every element in the submatrix immediately, we mark only the boundaries of each update. These boundary markers represent how the value should change when prefix sums are later computed across rows and columns.
After processing all queries, we run a prefix sum pass over the matrix to accumulate the increments and construct the final grid. This transforms repeated range updates into constant-time operations per query, making the solution far more scalable.
This approach significantly reduces the overall complexity while using only an auxiliary matrix for tracking updates.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Naive Submatrix Updates | O(q * n * n) | O(1) |
| 2D Difference Array + Prefix Sum | O(q + n^2) | O(n^2) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Imagine each row as a separate array. Instead of updating the whole submatrix together, we can use prefix sum to update each row separately.
For each query, iterate over the rows i in the range [row1, row2] and add 1 to prefix sum S[i][col1], and subtract 1 from S[i][col2 + 1].
After doing this operation for all the queries, update each row separately with S[i][j] = S[i][j] + S[i][j - 1].
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums allow you to convert multiple range updates into simple boundary operations. After marking updates, a cumulative sum pass efficiently spreads the increments to all affected cells.
Problems involving 2D prefix sums and range updates are common in technical interviews, including FAANG-style companies. This problem tests understanding of matrix manipulation, optimization, and prefix sum techniques.
A matrix-based difference array is the most suitable structure. It allows constant-time updates for each query and uses prefix sum calculations afterward to propagate the increments across the grid.
The optimal approach uses a 2D difference array combined with prefix sums. Instead of updating every cell in each submatrix, you mark only the boundaries of updates and later reconstruct the final matrix using prefix accumulation.