Cover image for Meta
See All Photos


Engaged Employer


Add an Interview

Interview Question

Machine Learning Software Engineer Interview



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

Interview Answers

7 Answers


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 on



Anonymous on


The answer is already popular in computer vision fields!! It is called integral imaging. See this page

seungwooYoo on


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];

Anonymous on


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.

Edi on


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

maxzed2k on


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.

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.

Meta Careers

Cover image for Meta

Bring the world closer together with Meta Meta builds technologies that help people connect, find communities and grow businesses. When...More

  • Our Technologies
  • The Metaverse
  • Meta and You
This is the employer's chance to tell you why you should work for them. The information provided is from their perspective.