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

Machine Learning Software Engineer Interview Palo Alto, CA

Facebook## 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?

Tags:

algorithm, code See More, See Less8

6 Answers

▲

1

▼

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

▲

14

▼

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).

▲

2

▼

Awesome!!

▲

3

▼

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

▲

4

▼

It wasn't 100% clear to me, then I found the Wiki page

http://en.wikipedia.org/wiki/Summed_area_table

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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.