304. Range Sum Query 2D - Immutable

Problem Description

We are given a 2D matrix matrix, and our task is to design a data structure that can efficiently calculate the sum of the elements within a rectangle defined by its upper-left and lower-right corners. The corner coordinates are given to us as (row1, col1) for the upper-left corner and (row2, col2) for the lower-right corner. This should be done for multiple queries and the data structure has to be efficient enough to provide the sum in constant time (O(1)).

Intuition

The key to solving this problem efficiently lies in preprocessing the matrix in such a way that it allows us to perform queries in O(1) time. This is achieved by computing a prefix sum matrix which is essentially a preprocessing step that facilitates quick sum retrieval.

The intuition behind using a prefix sum is that we can calculate the sum of a certain rectangle by combining the sums of different regions which are precomputed. The sum of elements inside the rectangle can be determined by adding and subtracting certain sums at key points that represent the corners of the rectangle.

To compute the prefix sum, we follow these steps:

1. Initialize an auxiliary matrix s with dimensions (m+1)x(n+1), where m is the number of rows in the input matrix and n is the number of columns. We use an extra row and column to handle zero scenarios without special cases.

2. We iterate through each element (i, j) of the original matrix and calculate s[i + 1][j + 1] as the sum of elements above and to the left including matrix[i][j]. This sum is computed by adding the sum up to the previous row (s[i][j + 1]), the sum up to the previous column (s[i + 1][j]), and then subtracting the sum that is double-counted (s[i][j]) because it was included in both previous sums, and finally adding the current element (matrix[i][j]).

3. Once the prefix sum matrix is created in the initialization process, the sum region can be computed by using the formula derived from the properties of the prefix sum matrix. The sum of a rectangle from (row1, col1) to (row2, col2) is computed by summing the cumulative sum at (row2 + 1, col2 + 1) and subtracting the areas that extend beyond the target rectangle (cumulative sum at (row2 + 1, col1), (row1, col2 + 1)), and adding back the area that was subtracted twice, which is at (row1, col1).

This technique harnesses the power of cumulative sums to facilitate rapid sum queries of rectangular submatrices and is particularly useful when there are multiple queries on the same initial matrix, greatly reducing the time complexity from O(m*n) to O(1) for each query after an O(m*n) preprocessing time.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation of the solution is straightforward once we understand the concept of a prefix sum matrix. Let's break down the approach and the pattern used in the given solution:

1. Construction of the Prefix Sum Matrix:

   • We start by creating a 2D array self.s which will store the prefix sums. Notice that this array has an extra row and column (m + 1 and n + 1), this is done to accommodate sums of submatrices that may include the first row or column without having to handle special cases.
   • We iterate through the original matrix, and for each element at (i, j) in matrix, we compute the prefix sum using:

     1self.s[i + 1][j + 1] = self.s[i][j + 1] + self.s[i + 1][j] - self.s[i][j] + matrix[i][j]

     In this formula:
     • self.s[i][j + 1] represents the sum of elements above the current element (up to the previous row).
     • self.s[i + 1][j] represents the sum of elements to the left of the current element (up to the previous column).
     • self.s[i][j] is the area that was added twice (once in above sum and once in left sum) and needs to be subtracted out.
     • matrix[i][j] is the value of the current element which needs to be added to complete the sum of the submatrix that ends at (i, j).

2. Sum Region Query:

   • Once the prefix sum matrix is constructed, we can answer any sum region query in O(1) time. The function sumRegion(row1, col1, row2, col2) computes the sum of the elements inside the rectangle using:

     1return (self.s[row2 + 1][col2 + 1] - self.s[row2 + 1][col1] - self.s[row1][col2 + 1] + self.s[row1][col1])

     Here's how the terms of the formula correspond to the regions:
     • self.s[row2 + 1][col2 + 1] gives the sum of all elements up to (row2, col2).
     • self.s[row2 + 1][col1] subtracts out the area to the left of col1 since it's not part of the desired rectangle.
     • self.s[row1][col2 + 1] subtracts out the area above row1.
     • self.s[row1][col1] adds back the area that was subtracted out twice (once for left and once for top).

Utilizing the prefix sum method provides a powerful way to carry out cumulative sum operations both efficiently and swiftly, thus making it a preferred approach for this type of problem.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach to the described problem. Assume we have the following 2D matrix:

1matrix = [
2  [3, 0, 1, 4, 2],
3  [5, 6, 3, 2, 1],
4  [1, 2, 0, 1, 5],
5  [4, 1, 0, 1, 7],
6  [1, 0, 3, 0, 5]
7]

1. Construction of the Prefix Sum Matrix:
   • We initiate an auxiliary array self.s with an extra row and column. Initially, it will look like this (we fill the extra row and column with 0s):

1self.s = [
2  [0, 0, 0, 0, 0, 0],
3  [0, 0, 0, 0, 0, 0],
4  [0, 0, 0, 0, 0, 0],
5  [0, 0, 0, 0, 0, 0],
6  [0, 0, 0, 0, 0, 0],
7  [0, 0, 0, 0, 0, 0]
8]

• We proceed to calculate the prefix sums for each cell based on the elements of the original matrix. For the first element (at 0, 0 in the original matrix), the sum will just be the element itself:

1self.s[1][1] = matrix[0][0] = 3
2
3// The matrix self.s would look like this after this step:
4self.s = [
5  [0, 0, 0, 0, 0, 0],
6  [0, 3, 0, 0, 0, 0],
7  ...
8]

• We fill in the rest of self.s using the formula detailed earlier. The fully filled prefix sum matrix would look like this:

1self.s = [
2  [0, 0,  0,  0,  0, 0],
3  [0, 3,  3,  4,  8, 10],
4  [0, 8, 14, 18, 24, 27],
5  [0, 9, 17, 21, 28, 36],
6  [0, 13,22, 26, 34, 49],
7  [0, 14,23, 30, 38, 58]
8]

2. Sum Region Query:
   • Let's say we wish to get the sum of elements within the rectangle defined by the corners (row1, col1) = (2, 1) and (row2, col2) = (4, 3). Following the formula provided, we calculate this as follows:

1sum = self.s[4 + 1][3 + 1] - self.s[4 + 1][1] - self.s[2][3 + 1] + self.s[2][1]
2    = self.s[5][4] - self.s[5][1] - self.s[2][4] + self.s[2][1]
3    = 38 - 14 - 24 + 8
4    = 8

This gives us the sum of elements in the rectangle defined from (2, 1) to (4, 3) which includes the values [2, 0, 1], [1, 0, 1], [0, 3, 0] from the original matrix.

This example demonstrates the efficiency of the prefix sum matrix in answering sum region queries in constant time after the preprocessing step has been completed.

Solution Implementation

Time and Space Complexity

The time complexity for initializing the NumMatrix object is O(m * n) where m is the number of rows and n is the number of columns in the input matrix. This is because we have two nested loops each going through m rows and n columns to compute the sum of each submatrix ending at (i, j).

The time complexity for the sumRegion query operation is O(1) because it involves a constant number of mathematical operations irrespective of the size of the input matrix or the selected region. It directly uses the precomputed sums from the self.s matrix to calculate the sum of the given region.

The space complexity of the code is also O(m * n) due to the additional space used to store the precomputed sums in the self.s matrix, which has the dimensions of (m + 1) * (n + 1) to allow for easier calculation of sums for the sumRegion method.

Learn more about how to find time and space complexity quickly using problem constraints.