Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this?

Question

Anonymous · Accepted Answer

Compute the sum of the rectangles, for all i,j,  bounded by (i,j), (i,m), (n,j), (n,m), where (n,m) is the size of the matrix M. Call that sum s(i,j). You can calculate s(i,j) by dynamic programming: s(i,j) = M(i,j) + s(i+1,j) + s(i,j+1) - s(i+1,j+1). And the sum of any rectangle can be computed from s(i,j).

Anonymous · Answer

It can be done in constant time by precalculating sums of some basic rectangles (extending all the way to the border of the matrix). That precalculation times time O(n) by simple dynamic programming.

seungwooYoo · Answer

The answer is already popular in computer vision fields!! It is called integral imaging. 
See this page http://en.wikipedia.org/wiki/Haar-like_features

Anonymous · Answer

Awesome!!

maxzed2k · Answer

Please elaborate, which "basic rectangles"? Are you recursively dividing each rectangle into 4 smaller rectangles? Precalc time for doing that is not O(n)?!?

Anonymous · Answer

Let a[][] be the 2d array, int i=0; for( j = row_start; j <= row_end; j++) for( k = col_start; k <= col_end; k++) i+=a[j][k];

Edi · Answer

Iterate over matrix as an array storing (new sums array) in each position the cumulative sum up to that point. For each row in the desired submatrix we can compute its sum as a difference between its end and start positions. Repeat for other rows. Add up all the row sums.

Meta

Meta interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?