Increment Submatrices by One
MedPrompt
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:
- Add
1to every element in the submatrix with the top left corner(row1i, col1i)and the bottom right corner(row2i, col2i). That is, add1tomat[x][y]for allrow1i <= x <= row2iandcol1i <= 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 < n
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We initialize an n x n matrix with zeros. Then, for each query, we iterate over all the cells within the specified rectangular submatrix and increment their values by one.
Algorithm
- Initialize an
n x nmatrixmatwith all zeros. - Iterate through each query
[row1, col1, row2, col2]in thequeriesarray. - For each query, use nested loops to iterate through every cell
(i, j)in the submatrix defined by the query, whererow1 <= i <= row2andcol1 <= j <= col2. - Inside the inner loop, increment the value of
mat[i][j]by 1. - After iterating through all queries, return the final
mat.
Walkthrough
The brute-force method is the most intuitive way to solve the problem. It follows the problem statement literally.
- We start by creating the
n x nmatrix,mat, and filling it with zeros. - We then loop through the
queriesarray. Each element in this array is another array representing a single query:[row1, col1, row2, col2]. - For each query, we use a pair of nested loops. The outer loop runs from
row1torow2, and the inner loop runs fromcol1tocol2. These loops cover every cell in the submatrix. - In the body of the inner loop, we simply perform the operation
mat[i][j]++. - After the outer loop finishes processing all the queries, the
matwill hold the final values, and we return it.
class Solution { public int[][] rangeAddQueries(int n, int[][] queries) { int[][] mat = new int[n][n]; for (int[] query : queries) { int row1 = query[0]; int col1 = query[1]; int row2 = query[2]; int col2 = query[3]; for (int i = row1; i <= row2; i++) { for (int j = col1; j <= col2; j++) { mat[i][j]++; } } } return mat; }}Complexity
Time
O(q * n^2) - Let `q` be the number of queries. For each query, in the worst case, we might have to update all `n*n` cells of the matrix (e.g., a query `[0, 0, n-1, n-1]`). This leads to a total time complexity proportional to the number of queries multiplied by the size of the matrix.
Space
O(n^2) - We need to store the `n x n` matrix.
Trade-offs
Pros
Simple to understand and implement.
Correct for all valid inputs, assuming no time constraints.
Cons
Highly inefficient for large inputs, especially when the submatrices in queries are large.
Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits due to its high time complexity.
This optimized approach uses a technique known as a 2D difference array (or 2D prefix sum). Instead of updating every cell in a submatrix for each query, we only mark the boundaries of the submatrix in an auxiliary matrix. A single +1 operation on a submatrix can be represented by four updates on the corners of the region. After processing all queries in this manner, we can reconstruct the final matrix from the difference matrix in a single pass using prefix sum calculations.
Algorithm
- Initialize an
n x nmatrixmatwith all zeros. This matrix will be used as a difference array. - For each query
[r1, c1, r2, c2], update four points in themat:mat[r1][c1]++mat[r1][c2 + 1]--(ifc2 + 1 < n)mat[r2 + 1][c1]--(ifr2 + 1 < n)mat[r2 + 1][c2 + 1]++(ifr2 + 1 < nandc2 + 1 < n)
- After processing all queries, transform the difference matrix
matinto the final result matrix using 2D prefix sums. - First, calculate prefix sums for each row:
mat[i][j] += mat[i][j-1]. - Then, calculate prefix sums for each column:
mat[i][j] += mat[i-1][j]. - Return the modified
mat.
Walkthrough
The key idea is to avoid redundant work. A single query affects a rectangular region. We can represent this update by making changes only at the corners of this region in a temporary 'difference' matrix.
- We initialize an
n x nmatrix,mat, with zeros. We will use this matrix to store the differences. - For each query
[r1, c1, r2, c2], we apply four changes:mat[r1][c1]++: This marks the top-left corner. When we later compute prefix sums, this+1will propagate to all cells(i, j)wherei >= r1andj >= c1.mat[r1][c2 + 1]--(ifc2 + 1 < n): This cancels the effect of the+1for all cells in the same rows but to the right of the submatrix (j > c2).mat[r2 + 1][c1]--(ifr2 + 1 < n): This cancels the effect for all cells in the same columns but below the submatrix (i > r2).mat[r2 + 1][c2 + 1]++(if bothr2 + 1 < nandc2 + 1 < n): The previous two subtractions have double-cancelled the effect for the regioni > r2andj > c2. We add1back to correct this.
- After all queries are processed,
matholds the difference information. We now need to convert it to the actual values by computing 2D prefix sums. - First, we iterate through each row and compute its prefix sum:
for i from 0 to n-1, for j from 1 to n-1, mat[i][j] += mat[i][j-1]. - Next, we iterate through each column and compute its prefix sum:
for j from 0 to n-1, for i from 1 to n-1, mat[i][j] += mat[i-1][j]. - The resulting
matis the final answer.
class Solution { public int[][] rangeAddQueries(int n, int[][] queries) { int[][] mat = new int[n][n]; // Step 1: Apply all query operations on the difference matrix for (int[] q : queries) { int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3]; mat[r1][c1]++; if (c2 + 1 < n) { mat[r1][c2 + 1]--; } if (r2 + 1 < n) { mat[r2 + 1][c1]--; } if (r2 + 1 < n && c2 + 1 < n) { mat[r2 + 1][c2 + 1]++; } } // Step 2: Reconstruct the matrix from the differences using 2D prefix sums // First pass: row-wise prefix sums for (int i = 0; i < n; i++) { for (int j = 1; j < n; j++) { mat[i][j] += mat[i][j - 1]; } } // Second pass: column-wise prefix sums for (int j = 0; j < n; j++) { for (int i = 1; i < n; i++) { mat[i][j] += mat[i - 1][j]; } } return mat; }}Complexity
Time
O(q + n^2) - Let `q` be the number of queries. Processing all queries takes O(q) time, as each query involves a constant number of operations (at most 4). Reconstructing the final matrix from the difference matrix takes O(n^2) time. The total complexity is dominated by the larger of these two terms.
Space
O(n^2) - We use an `n x n` matrix to store the differences and then the final result. No extra space beyond the result matrix is needed if done in-place.
Trade-offs
Pros
Very efficient, especially for a large number of queries.
Reduces the complexity of processing queries from O(n^2) per query to O(1) per query.
Cons
The logic is more complex to understand compared to the brute-force approach.
It still requires O(n^2) space, which can be large for a very large
n.
Solutions
Solution
class Solution {public int[][] rangeAddQueries(int n, int[][] queries) { int[][] mat = new int[n][n]; for (var q : queries) { int x1 = q[0], y1 = q[1], x2 = q[2], y2 = q[3]; mat[x1][y1]++; if (x2 + 1 < n) { mat[x2 + 1][y1]--; } if (y2 + 1 < n) { mat[x1][y2 + 1]--; } if (x2 + 1 < n && y2 + 1 < n) { mat[x2 + 1][y2 + 1]++; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i > 0) { mat[i][j] += mat[i - 1][j]; } if (j > 0) { mat[i][j] += mat[i][j - 1]; } if (i > 0 && j > 0) { mat[i][j] -= mat[i - 1][j - 1]; } } } return mat; }}class Solution {public: vector<vector<int>> rangeAddQueries(int n, vector<vector<int>> &queries) { vector<vector<int>> mat(n, vector<int>(n)); for (auto &q : queries) { int x1 = q[0], y1 = q[1], x2 = q[2], y2 = q[3]; mat[x1][y1]++; if (x2 + 1 < n) { mat[x2 + 1][y1]--; } if (y2 + 1 < n) { mat[x1][y2 + 1]--; } if (x2 + 1 < n && y2 + 1 < n) { mat[x2 + 1][y2 + 1]++; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i > 0) { mat[i][j] += mat[i - 1][j]; } if (j > 0) { mat[i][j] += mat[i][j - 1]; } if (i > 0 && j > 0) { mat[i][j] -= mat[i - 1][j - 1]; } } } return mat; }};class Solution: def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]: mat = [[0] * n for _ in range(n)] for x1, y1, x2, y2 in queries: mat[x1][y1] += 1 if x2 + 1 < n: mat[x2 + 1][y1] -= 1 if y2 + 1 < n: mat[x1][y2 + 1] -= 1 if x2 + 1 < n and y2 + 1 < n: mat[x2 + 1][y2 + 1] += 1 for i in range(n): for j in range(n): if i: mat[i][j] += mat[i - 1][j] if j: mat[i][j] += mat[i][j - 1] if i and j: mat[i][j] -= mat[i - 1][j - 1] return matVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.