2536. Increment Submatrices by One
Problem Description
We start with an n x n
matrix mat
filled with zeroes, and we are tasked to perform a series of operations based on a list of queries, each represented by [row1, col1, row2, col2]
. For each query, we increment by 1
every element in the submatrix with its top left corner at (row1, col1)
and its bottom right corner at (row2, col2)
. After performing all queries, we need to return the final resulting matrix.
The main challenge is to perform these updates efficiently since applying each query individually could lead to a time complexity that is too high if the number of queries or the size of the matrix is large.
Intuition
The intuition behind the solution lies in using the concept of [prefix sum](/problems/subarray_sum)
in a two-dimensional space, which is an extension of the prefix sum algorithm used for one-dimensional arrays.
In one-dimensional space, the prefix sum at any point i
represents the sum of all elements from index 0
to i
. In two-dimensional space, we extend this concept to both rows and columns. So at any point (i, j)
in the mat
, we intend to store the sum of all elements in the submatrix whose top left corner is (0, 0)
and the bottom right corner is (i, j)
.
We can achieve this efficiently using a technique called difference array
. Instead of incrementing all elements within the submatrix specified by the query, we only increment the top left corner element by 1
, and then decrement the elements just outside the lower and right bounds by -1
. This marks the boundaries of the region that should be increased.
Once the boundary updates for all queries are made, we re-construct the actual matrix by computing prefix sums row-wise and column-wise. These prefix sums account for the boundaries we've marked earlier, and effectively simulate the addition of 1
across the entire submatrix for each query.
By processing the updates this way, we make the operation for each query independent of the size of the submatrix, therefore, improving the efficiency of the solution significantly.
Learn more about Prefix Sum patterns.
Solution Approach
The solution approach uses the following key steps which are reflected in the provided code:
-
Initialize a matrix
mat
of sizen x n
filled with zeroes. -
Process each query
[x1, y1, x2, y2]
to update the matrix boundaries:- Increment the element at the top left corner
(x1, y1)
of the submatrix by1
to indicate the start of a region where every element should be incremented. - Decrement the element just outside the bottom boundary
(x2 + 1, y1)
and right boundary(x1, y2 + 1)
to fix the overestimated addition if it's within matrix bounds. This is because when we later calculate the prefix sum, this decrement will cancel out the increments for elements beyond the submatrix' boundaries. - If the bottom right corner
(x2 + 1, y2 + 1)
is inside the bounds of the matrix, increment it to counter the extra decrement that occurs when both the right boundary and bottom boundary adjustments overlap.
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
- Increment the element at the top left corner
-
Construct the final matrix by computing the prefix sum:
- Accumulate the sums in the
mat
matrix row-wise and column-wise. The current elementmat[i][j]
is updated by accumulating the value from the topmat[i-1][j]
if it exists, from the leftmat[i][j-1]
if it exists, and then subtracting the top-left diagonalmat[i-1][j-1]
if it exists to avoid double-counting.
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]
- Accumulate the sums in the
The final mat
after this step contains the answer.
By following these steps, the code employs a clever bookkeeping strategy to efficiently update the matrix for each query, transforming what would be a potentially quadratic per-query operation into a linear one (with respect to the size of the matrix). The use of boundary marking and prefix sums is the crux of this efficient solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a 3 x 3
matrix and a list of queries [[0, 0, 1, 1], [1, 1, 2, 2]]
to illustrate the solution approach.
Initially, the matrix mat
is filled with zeros:
0 0 0 0 0 0 0 0 0
Now let's apply the queries:
- For the first query
[0, 0, 1, 1]
, we incrementmat[0][0]
by 1, decrementmat[2][0]
andmat[0][2]
by 1 (which are outside of our matrix bounds, so we ignore in this case), and sincemat[2][2]
is outside our matrix bounds, there are no operations. After this query,mat
looks like:
1 0 0 0 0 0 0 0 0
- The second query
[1, 1, 2, 2]
instructs us to incrementmat[1][1]
by 1, decrementmat[3][1]
andmat[1][3]
by 1 (again outside of our matrix bounds), and incrementmat[3][3]
(which is also outside of our bounds). After this query,mat
looks like:
1 0 0 0 1 0 0 0 0
Now, we need to construct the final matrix by computing the prefix sum row-wise and column-wise:
- Starting at
mat[0][0]
, we move right. There are no previous elements, so we keep moving across the first row:
1 1 1 0 1 0 0 0 0
- Now we move down to the next row,
mat[1][0]
, adding the value above, so we get1
inmat[1][0]
. We do the same across the second row:
1 1 1 1 2 1 0 0 0
- Finally, we process the last row in the same way. Start at
mat[2][0]
, addmat[1][0]
tomat[2][0]
to get1
and continue the process for the row:
1 1 1 1 2 1 1 1 1
The final matrix now accurately reflects the result after applying the given list of queries, according to the described solution approach:
1 1 1 1 2 1 1 1 1
The example demonstrates how the solution approach efficiently updates the entire matrix using boundary marking and prefix sums, avoiding incrementing every single element within each target submatrix for the queries given.
Solution Implementation
1from typing import List
2
3class Solution:
4 def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
5 # Create a matrix initialized with zeros
6 matrix = [[0] * n for _ in range(n)]
7
8 # Apply the query operations using a prefix sum approach
9 for x1, y1, x2, y2 in queries:
10 # Increment the top-left corner of the range by 1
11 matrix[x1][y1] += 1
12
13 # Decrement the positions just outside the range
14 if x2 + 1 < n:
15 matrix[x2 + 1][y1] -= 1
16 if y2 + 1 < n:
17 matrix[x1][y2 + 1] -= 1
18 if x2 + 1 < n and y2 + 1 < n:
19 # This position was decremented twice, so we increment it once
20 matrix[x2 + 1][y2 + 1] += 1
21
22 # Convert the operations to actual values by propagating the increments
23 for i in range(n):
24 for j in range(n):
25 # If not in the first row, add value from the cell directly above
26 if i > 0:
27 matrix[i][j] += matrix[i - 1][j]
28 # If not in the first column, add value from the cell directly to the left
29 if j > 0:
30 matrix[i][j] += matrix[i][j - 1]
31 # If not in the first row or column, subtract the value from
32 # the cell to the top-left to counteract double counting
33 if i > 0 and j > 0:
34 matrix[i][j] -= matrix[i - 1][j - 1]
35
36 # The resultant matrix contains the final values after all queries
37 return matrix
38
1class Solution {
2 public int[][] rangeAddQueries(int n, int[][] queries) {
3 // Initialize the matrix with size n x n and all values set to 0
4 int[][] matrix = new int[n][n];
5 // Process each query to increment the corners of the submatrix
6 for (int[] query : queries) {
7 int startX = query[0], startY = query[1], endX = query[2], endY = query[3];
8 matrix[startX][startY]++; // Top-left corner
9
10 // Prevent out of bounds and mark just outside the bottom boundary if within limits
11 if (endX + 1 < n) {
12 matrix[endX + 1][startY]--;
13 }
14
15 // Prevent out of bounds and mark just outside the right boundary if within limits
16 if (endY + 1 < n) {
17 matrix[startX][endY + 1]--;
18 }
19
20 // Adjust for overlap by incrementing the bottom-right corner outside of the submatrix
21 if (endX + 1 < n && endY + 1 < n) {
22 matrix[endX + 1][endY + 1]++;
23 }
24 }
25
26 // Cumulative sum logic to update the matrix values to reflect all range queries
27 for (int i = 0; i < n; ++i) {
28 for (int j = 0; j < n; ++j) {
29 if (i > 0) {
30 // Add the value from the previous row to accumulate the vertical sums
31 matrix[i][j] += matrix[i - 1][j];
32 }
33 if (j > 0) {
34 // Add the value from the previous column to accumulate the horizontal sums
35 matrix[i][j] += matrix[i][j - 1];
36 }
37 if (i > 0 && j > 0) {
38 // Subtract the overlapping value that has been added twice
39 matrix[i][j] -= matrix[i - 1][j - 1];
40 }
41 }
42 }
43 // Return the updated matrix after processing all the range add queries
44 return matrix;
45 }
46}
47
1class Solution {
2public:
3 vector<vector<int>> rangeAddQueries(int size, vector<vector<int>>& queries) {
4 // Initialize the matrix 'resultMatrix' with 'size' rows and columns filled with zeros
5 vector<vector<int>> resultMatrix(size, vector<int>(size, 0));
6
7 // Process each range add query
8 for (auto& query : queries) {
9 // Retrieve the range's top-left and bottom-right coordinates
10 int topLeftRow = query[0], topLeftCol = query[1],
11 bottomRightRow = query[2], bottomRightCol = query[3];
12
13 // Increment value at the top-left corner of the range
14 resultMatrix[topLeftRow][topLeftCol]++;
15
16 // If the range extends beyond the bottom border of the matrix,
17 // decrement the value just outside the bottom border of the range
18 if (bottomRightRow + 1 < size) {
19 resultMatrix[bottomRightRow + 1][topLeftCol]--;
20 }
21
22 // If the range extends beyond the right border of the matrix,
23 // decrement the value just outside the right border of the range
24 if (bottomRightCol + 1 < size) {
25 resultMatrix[topLeftRow][bottomRightCol + 1]--;
26 }
27
28 // If the range extends beyond both the bottom and right borders of the matrix,
29 // increment the value at the coordinate just outside the bottom-right corner of the range (to cancel out the double subtraction)
30 if (bottomRightRow + 1 < size && bottomRightCol + 1 < size) {
31 resultMatrix[bottomRightRow + 1][bottomRightCol + 1]++;
32 }
33 }
34
35 // Propagate the range additions through the entire matrix
36 for (int i = 0; i < size; ++i) {
37 for (int j = 0; j < size; ++j) {
38 // If not at the first row, add value from the cell directly above
39 if (i > 0) {
40 resultMatrix[i][j] += resultMatrix[i - 1][j];
41 }
42
43 // If not at the first column, add value from the cell directly left
44 if (j > 0) {
45 resultMatrix[i][j] += resultMatrix[i][j - 1];
46 }
47
48 // If not at the first row or column, subtract the value from the top-left diagonal to avoid double counting
49 if (i > 0 && j > 0) {
50 resultMatrix[i][j] -= resultMatrix[i - 1][j - 1];
51 }
52 }
53 }
54
55 // Return the resulting matrix after all range additions have been applied
56 return resultMatrix;
57 }
58};
59
1function rangeAddQueries(size: number, queries: number[][]): number[][] {
2 // Initialize the resultMatrix with 'size' rows and columns filled with zeros
3 const resultMatrix: number[][] = Array.from({ length: size }, () => new Array(size).fill(0));
4
5 // Process each range add query
6 for (const query of queries) {
7 // Retrieve the range's top-left and bottom-right coordinates
8 const topLeftRow = query[0],
9 topLeftCol = query[1],
10 bottomRightRow = query[2],
11 bottomRightCol = query[3];
12
13 // Increment value at the top-left corner of the range
14 resultMatrix[topLeftRow][topLeftCol]++;
15
16 // If the range extends beyond the bottom border of the matrix,
17 // decrement the value just outside the bottom border of the range
18 if (bottomRightRow + 1 < size) {
19 resultMatrix[bottomRightRow + 1][topLeftCol]--;
20 }
21
22 // If the range extends beyond the right border of the matrix,
23 // decrement the value just outside the right border of the range
24 if (bottomRightCol + 1 < size) {
25 resultMatrix[topLeftRow][bottomRightCol + 1]--;
26 }
27
28 // If the range extends beyond both the bottom and right borders of the matrix,
29 // increment the value at the coordinate just outside the bottom-right corner of the range
30 if (bottomRightRow + 1 < size && bottomRightCol + 1 < size) {
31 resultMatrix[bottomRightRow + 1][bottomRightCol + 1]++;
32 }
33 }
34
35 // Propagate the range additions through the entire matrix
36 for (let i = 0; i < size; i++) {
37 for (let j = 0; j < size; j++) {
38 // If not at the first row, add value from the cell directly above
39 if (i > 0) {
40 resultMatrix[i][j] += resultMatrix[i - 1][j];
41 }
42
43 // If not at the first column, add value from the cell directly to the left
44 if (j > 0) {
45 resultMatrix[i][j] += resultMatrix[i][j - 1];
46 }
47
48 // If not at the first row or column, subtract the value from the top-left diagonal to avoid double counting
49 if (i > 0 && j > 0) {
50 resultMatrix[i][j] -= resultMatrix[i - 1][j - 1];
51 }
52 }
53 }
54
55 // Return the resulting matrix after all range additions have been applied
56 return resultMatrix;
57}
58
Time and Space Complexity
The provided code aims to perform range additions for a matrix of size n x n
based on a list of queries. Each query consists of coordinates defining the top-left (x1, y1)
and bottom-right (x2, y2)
corners of a submatrix where the values should be incremented by 1.
Time Complexity
The time complexity of the code can be analyzed by breaking it down into two parts:
-
Processing the queries:
- The queries are processed one by one in a loop. For each query, there are constant time updates being made to the matrix
mat
. Consequently, this part has a time complexity ofO(Q)
, whereQ
is the number of queries.
- The queries are processed one by one in a loop. For each query, there are constant time updates being made to the matrix
-
Prefix Sum Calculation:
- After processing the queries, two nested loops are used to calculate the prefix sums over the matrix. Each element in the matrix is visited and updated based on the values of its neighbors. Therefore, this part has a time complexity of
O(n^2)
, since we iterate over all elements of then x n
matrix.
- After processing the queries, two nested loops are used to calculate the prefix sums over the matrix. Each element in the matrix is visited and updated based on the values of its neighbors. Therefore, this part has a time complexity of
Combining both parts, the overall time complexity is O(Q + n^2)
.
Space Complexity
The space complexity is determined by the memory required for the input and the internal data structures used by the algorithm.
-
The matrix
mat
is the main data structure with a size ofn x n
, so it has a space complexity ofO(n^2)
. -
No additional significant space is used, so the space complexity remains
O(n^2)
overall.
Hence, the time complexity of the code is O(Q + n^2)
and the space complexity is O(n^2)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!