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:

  1. Initialize a matrix mat of size n x n filled with zeroes.

  2. 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 by 1 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
  3. Construct the final matrix by computing the prefix sum:

    • Accumulate the sums in the mat matrix row-wise and column-wise. The current element mat[i][j] is updated by accumulating the value from the top mat[i-1][j] if it exists, from the left mat[i][j-1] if it exists, and then subtracting the top-left diagonal mat[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]

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 Evaluator

Example 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:

  1. For the first query [0, 0, 1, 1], we increment mat[0][0] by 1, decrement mat[2][0] and mat[0][2] by 1 (which are outside of our matrix bounds, so we ignore in this case), and since mat[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
  1. The second query [1, 1, 2, 2] instructs us to increment mat[1][1] by 1, decrement mat[3][1] and mat[1][3] by 1 (again outside of our matrix bounds), and increment mat[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:

  1. 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
  1. Now we move down to the next row, mat[1][0], adding the value above, so we get 1 in mat[1][0]. We do the same across the second row:
1 1 1
1 2 1
0 0 0
  1. Finally, we process the last row in the same way. Start at mat[2][0], add mat[1][0] to mat[2][0] to get 1 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:

  1. 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 of O(Q), where Q is the number of queries.
  2. 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 the n x n matrix.

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.

  1. The matrix mat is the main data structure with a size of n x n, so it has a space complexity of O(n^2).

  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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement recursion?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More