Menu
In an interview I was asked if I was given an n*m matrix how to calculate the sum of the values in a given sub-matrix (defined by top-left, bottom-right coordinates).
I was told I could pre-process the matrix.
I was told the matrix could be massive and so could the sub-matrix so the algo had to be efficient. I stumbled a bit and wasn't told the best answer.
Anyone have a good answer?
674
Description. S = sum( A ) returns the sum of the elements of A along the first array dimension whose size does not equal 1. If A is a vector, then sum(A) returns the sum of the elements. If A is a matrix, then sum(A) returns a row vector containing the sum of each column.
The SUMPRODUCT function returns the sum of the products of corresponding ranges or arrays.
The idea is to first create an auxiliary matrix aux[M][N] such that aux[i][j] stores sum of elements in submatrix from (0,0) to (i,j). Once aux[][] is constructed, we can compute sum of submatrix between (tli, tlj) and (rbi, rbj) in O(1) time.
This is what Summed Area Tables are for. http://en.wikipedia.org/wiki/Summed_area_table
Your "preprocessing" step is to build a new matrix of the same size, where each entry is the sum of the sub-matrix to the upper-left of that entry. Any arbitrary sub-matrix sum can be calculated by looking up and mixing only 4 entries in the SAT.
EDIT: Here's an example.
For the initial matrix
0 1 4 2 3 2 1 2 7 The SAT is
0 1 5 2 6 12 3 9 22 The SAT is obtained using S(x,y) = a(x,y) + S(x-1,y) + S(x,y-1) - S(x-1,y-1),
where S is the SAT matrix and a is the initial matrix .
If you want the sum of the lower-right 2x2 sub-matrix, the answer would be 22 + 0 - 3 - 5 = 14. Which is obviously the same as 3 + 2 + 2 + 7. Regardless of the size of the matrix, the sum of a sub matrix can be found in 4 lookups and 3 arithmetic ops. Building the SAT is O(n), similarly requiring only 4 lookups and 3 math ops per cell.
139
You can do it by Dynamic programming. Create matrix dp with size n*m. And for each i, j where
1 <= i <= n , 1 <= j <= m dp[i][j] will be : dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + values[i][j] And for each query we have lx, rx, ly, ry where lx and rx are top-left coordinates, ly and ry bottom-right coordinates of sub-matrix.
1 ≤ lxi ≤ rx ≤ n, 1 ≤ ly ≤ ry ≤ m sum = dp[rx][ry] - dp[lx - 1][ry] - dp[rx][ly - 1] + dp[lx-1][ly - 1] Look at picture to understand how algorithm works.
OD = dp[rx][ry], OB = dp[lx - 1][ry], OC = dp[rx][ly - 1], OA = dp[lx - 1][ly - 1] 
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With