Programming Interview Questions 2: Matrix Region Sum

This is a very elegant question which seems easy at first but requires some hard thinking to solve it efficiently: Given a matrix of integers and coordinates of a rectangular region within the matrix, find the sum of numbers falling inside the rectangle. Our program will be called multiple times with different rectangular regions from the same matrix.


It seems very easy right? Just write a double for loop and sum up the numbers. Given the integer matrix, top left and bottom right coordinates of the rectangular region, the algorithm would simply be:

def matrixRegionSum1(matrix, A, D):
    if len(matrix)==0:
        return
    totalSum=0
    for i in range(A[0], D[0]+1):
        for j in range(A[1], D[1]+1):
            totalSum+=matrix[i][j]
    return totalSum

The complexity of this solution is O(MN) where M is the number of rows of the matrix, and N is the number of columns. This is a fairly straightforward solution that initially comes to mind. However, it’s far from optimal because we’re not caching any data and all the subsequent calls to the program has the same complexity. Since this routine will be executed multiple times, ideally we want every call to the function to take constant O(1) time without using too much extra space.

We should precompute and cache some data in order to reduce the complexity to O(1). The precomputation complexity is not that important since it will be performed just once in the beginning, and the cached data will be used to speed up the subsequent calls to the function. Let’s see what we can precompute. To achieve an O(1) solution, we can precompute the sum of every possible rectangular region inside the matrix, and store it in a hashtable for later use. Afterwards, when we are asked the sum of a rectangular region, we will just return the precomputed value in constant time. However, the space complexity of this approach would be O(M^2N^2) which is too much. Because there are MN different candidates for both top left and bottom right coordinates of the rectangle.

Precomputing and caching the sums of all rectangles results in a constant time algorithm, but it uses a lot of space. Let’s think whether we can reduce the space complexity to a reasonable amount. The main inefficiency was to store the sum of all possible rectangular regions, instead we can store a subset of them and still achieve constant complexity. Let’s calculate the sum of all rectangular regions whose top left corner is always the point ‘O’ in the above figure (top left corner of the matrix) and bottom right corner is any point in the matrix. By doing this we fix the top left coordinate of the precomputed regions and reduce the number of cached sums to O(MN), because only the bottom right corner of the rectangles is free. So the space complexity reduces to O(MN). Now the question is whether we can compute the sum of any rectangular region using only the precomputed sums of regions whose top left coordinate is the point ‘O’. Apparently we can, here is how it works:

Given a random rectangular region ABCD, we can calculate its sum using the sums of 4 precomputed rectangular regions all of which top left corner is the point ‘O’.

Sum(ABCD) = Sum(OD) - Sum(OB) - Sum(OC) + Sum(OA)

Elegant, isn’t it? Here is the code to precompute the sum of all rectangular regions whose top left coordinate is the point ‘O’. It uses dynamic programming to efficiently compute the sums. The complexity is O(MN) which is optimal because we wanted to compute the sum of MN different rectangular regions. So each region sum is computed in O(1) time by using the sum of the previous regions by dynamic programming.

def precomputeSums(matrix):
    topRow, bottomRow=(0, len(matrix)-1)
    leftCol, rightCol=(0, len(matrix[0])-1)
    sums=[[0]*(rightCol-leftCol+1) for i in range(bottomRow-topRow+1)]
    sums[topRow][leftCol]=matrix[topRow][leftCol]
 
    for col in range(leftCol+1, rightCol+1):
        sums[topRow][col]=sums[topRow][col-1]+matrix[topRow][col]
    for row in range(topRow+1, bottomRow+1):
        sums[row][leftCol]=sums[row-1][leftCol]+matrix[row][leftCol]
 
    for col in range(leftCol+1, rightCol+1):
        columnSum=matrix[topRow][col]
        for row in range(topRow+1, bottomRow+1):
            sums[row][col]=sums[row][col-1]+matrix[row][col]+columnSum
            columnSum+=matrix[row][col]
 
    return sums

Once we have the precomputed sums, we use the above formula to compute the sum of any rectangular region in O(1).

def matrixRegionSum2(matrix, A, D, sums):
    if len(matrix)==0:
        return
 
    if A[0]==0 or A[1]==0:
        OA=0
    else:
        OA=sums[A[0]-1][A[1]-1]
 
    if A[1]==0:
        OC=0
    else:
        OC=sums[D[0]][A[1]-1]
 
    if A[0]==0:
        OB=0
    else:
        OB=sums[A[0]-1][D[1]]
 
    OD=sums[D[0]][D[1]]
 
    return OD-OB-OC+OA

I personally like this question a lot because it demonstrates how an easy question can be solved very efficiently using precomputation, dynamic programming, and clever thinking.

VN:F [1.9.22_1171]
Rating: 9.2/10 (74 votes cast)
Programming Interview Questions 2: Matrix Region Sum, 9.2 out of 10 based on 74 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
  • umar

    Good Solution.
    I have seen your some posts. Very Good questions.
    Please write code in C++ also.
    Because some time understand is difficult.

    Thanks

  • http://www.cs.ucsb.edu/~prakash Prakash

    precompute can be done like this ..

    sum[0][0] = matrix[0][0]
    for first row
    sum[0][j] = sum[0][j-1] + matrix[0][j]
    for first column
    sum[i][0] = sum[i-1][0] + matrix[i][0]
    for all other rows and columns
    sum[i][j] = matrix[i][j] + sum[i-1][j] + sum[i][j-1] – sum[i-1][j-1]


    // a is input array .. filled with sample inputs
    int a[][] = {
    {1,1,1,1,1},
    {2,2,2,2,2},
    {3,3,3,3,3},
    {4,4,4,4,4},
    {5,5,5,5,5}
    };
    int sum[][] = new int[a.length][a[0].length];
    sum[0][0] = a[0][0];
    for(int i=1;i<a.length;i++){
    sum[i][0] = sum[i-1][0] + a[i][0];
    }
    for(int j=1;j<a[0].length;j++){
    sum[0][j] = sum[0][j-1] + a[0][j];
    }
    for(int i=1; i<a.length;i++) {
    for(int j=1; j<a[0].length;j++) {
    sum[i][j] = a[i][j]
    + sum[i][j-1]
    + sum[i-1][j]
    - sum[i-1][j-1];
    }
    }

  • umar

    @Thanks Prakash for C++ code.
    I understand the problem and solution but below code is difficult to understand
    can any one explain what we have to do when we calculate the sum and store it.

    What is in A and D?

    def matrixRegionSum2(matrix, A, D, sums):
    if len(matrix)==0:
    return

    if A[0]==0 or A[1]==0:
    OA=0
    else:
    OA=sums[A[0]-1][A[1]-1]

    if A[1]==0:
    OC=0
    else:
    OC=sums[D[0]][A[1]-1]

    if A[0]==0:
    OB=0
    else:
    OB=sums[A[0]-1][D[1]]

    OD=sums[D[0]][D[1]]

    return OD-OB-OC+OA

    • Arden

      A and D are the coordinates of the points shown in the figure. So both are just a pair of numbers (x and y coordinates). Once we compute the sums, we apply the above formula:
      Sum(ABCD) = Sum(OD) – Sum(OB) – Sum(OC) + Sum(OA)

      • Usman Munier

        How about getting sum this way in just 2 loops

        for(int i=0; i<matrix.length;i++) {

        for(int j=0; j0){

        System.out.println(matrix[i][j]);

        sum[i][j] =sum[i][j-1] +matrix[i][j];

        }else if(j==0 && i>0){

        System.out.println(matrix[i][j]);

        sum[i][j] = sum[i-1][j] + matrix[i][j];

        }else if(i>0 && j>0){

        sum[i][j] = matrix[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];

        }

        }

        }

  • Jester

    Thank you so much for such amazing solutions. Just for curiosity, lets say we were allowed to use only constant space. Would it be possible to get the sum in less than O(n^2) complexity?

    I was thinking of using the ‘type-writer’ way of summing up. i.e. start at A, keep going right until we cross over B. Here increase the Y counter and reset the X counter to A’s X cordinate. Keep doing this until the counters (i.e. X and Y) both fall outside the range of the rectangle. This is an O(n) time complexity algorithm which uses O(1) space.

    • http://cs.ucsb.edu/~prakash prakash

      i think we can’t find sum of n x n matrix in O(n) time ..

    • Arden

      With constant space computing the sum can’t be better than O(n^2). Because in the worst case we will have to read each element in the matrix at least once. Only with extra space and precomputation we can achieve better complexities.

  • Ashot Madatyan

    Hi Arden.
    That’s an elegant solution and, btw, this approach is also used in some computer graphics libraries to do fast calculation(processing) of rectangular regions defined by their coordinates. I remember having designed this same algorithm some 10-12 years ago for one of my DIP projects, before I came across the similar solutions in the graphics libraries.
    Anyway, thanks for posting this wonderful explanation, very good job done !!!

  • anki

    great work

  • aarthi

    please post ur logic in c or c++ its difficult to understand

    • inexperienced

      I don’t even know Python and I can understand this

  • Fatih

    Here is the C sharp code (both for constructing the matrix and making the computation)

    namespace MatrixRegionSum

    {

    class Matrix

    {

    int[,] matrix;

    int rowCount;

    int columnCount;

    int maximumCellValue;

    int[,] sumToPointFromLeftTop;

    public Matrix(int rowCount, int columnCount, int maximumCellValue)

    {

    this.rowCount = rowCount;

    this.columnCount = columnCount;

    this.maximumCellValue = maximumCellValue;

    matrix = new int[this.rowCount, this.columnCount];

    }

    public void populateTheMatrixRandomly()

    {

    Random random = new Random();

    for (int i = 0; i < rowCount; i++)

    {

    for (int k = 0; k < columnCount; k++)

    {

    int cellValue = random.Next(0,maximumCellValue);

    Console.WriteLine("Putting value:" + cellValue + " to the cell[" + i + "," + k + "]");

    matrix[i, k] = cellValue;

    }

    }

    }

    public void printMatrix()

    {

    for (int i = 0; i < rowCount; i++)

    {

    for (int k = 0; k < columnCount; k++)

    {

    Console.Write(matrix[i,k]+"t");

    }

    Console.WriteLine("n");

    }

    }

    public void calculateSumsFromLeftTop()

    {

    sumToPointFromLeftTop = new int[rowCount, columnCount];

    int i = 0;

    while (true)

    {

    int k = 0;

    while (true)

    {

    int sumToThatPoint = 0;

    for (int row = 0; row <= i; row++)

    {

    for (int column = 0; column 0)

    {

    lefRectangleSum = sumToPointFromLeftTop[x2, y1 – 1];

    }

    if (x1 > 0)

    {

    upperRectangleSum = sumToPointFromLeftTop[x1 – 1, y2];

    }

    if (y1 > 0 && x1 > 0)

    {

    intersectionRectangleSum = sumToPointFromLeftTop[x1 – 1, y1 – 1];

    }

    sum = firstRectangleSum – lefRectangleSum – upperRectangleSum + intersectionRectangleSum;

    Console.WriteLine(“Sum is: ” + sum);

    }

    }

    }

  • Jun

    In your precompute step, you can use a matrix one row and one col bigger than the original matrix, so that you do not have to explicitly consider the first row and first col.

    int length = matrix.length+1;
    int width = matrix[0].length+1;
    int[][] areaSum = new int[length][width];

    for (int i = 1; i < length; i++) {
    for (int j = 1; j < width; j++) {
    areaSum[i][j] = areaSum[i-1][j] + areaSum[i][j-1] – areaSum[i-1][j-1] + matrix[i-1][j-1];
    }
    }

  • Brice

    It’s a good way of working it out, but having the upfront cost bothers me. I understand the effectiveness with code that will be part of a tight loop or rendering cycle, but for other applications, I would rather build the table over time.

    Python makes this really easy too. Stick a memoizing decorator[1] on your function that calculates the value of area `O` and the efficiency will approach O(1) the more you use it without forcing an up-front cost, giving you best case O(1) and worst case O(mn), and improving efficiency with use. It will also be space efficient, especially in cases where certain ranges of areas are more likely to be requested than others.

    I prefer to do it this way, since you are guaranteed that both the total time performance and memory use will be better or identical to full upfront calculation. This is especially true if the probability of a given request (ABCD) is not flat across possible values of A,B,C and D, or if the number of requests over the lifetime of the program is much smaller that the number of points in the large matrix.

    Also, when you have the memoizing decorator, you can stick it onto the function that calculates the value of the area ABCD, and gain efficiency for repeated request, as you only have to do one lookup, rather than four lookups and three operations.

    [1]: http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

    • Saurabh

      It depends on what is the application of this algorithm. It’s alright if it takes some time for initialization, there are times when a fast and constant response time is required and is very important – think about a real time breaking system for bullet trains, you cannot risk a delay of those 0.00045 seconds because it’s a question of someone’s life and death.

      Saurabh

  • Usman Munier

    how about getting the sum in just 2 loop

    for(int i=0; i<matrix.length;i++) {

    for(int j=0; j0){

    System.out.println(matrix[i][j]);

    sum[i][j] =sum[i][j-1] +matrix[i][j];

    }else if(j==0 && i>0){

    System.out.println(matrix[i][j]);

    sum[i][j] = sum[i-1][j] + matrix[i][j];

    }else if(i>0 && j>0){

    sum[i][j] = matrix[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];

    }

    }

    }

  • Aryak

    I didn’t get this part, ” However, the space complexity of this approach would be O(M^2N^2) which is too much. Because there are MN different candidates for both top left and bottom right coordinates of the rectangle. “

    • Saurabh

      Aryak,
      The rectangle can be defined by two points – top left and bottom right. So, how many top left points can be in this case for MxN matrix? it’s M x N. And how many bottom right points can be? It’s again MxN.

      So how many total rectangles are possible?
      (MxN) x (MxN) = (MN)2 = M2N2 (m square n square)

      And we have to store the value for every possible rectangle that can be formed? So we need those many memory locations/spaces. Hence, space complexity is O(M2N2).

      Saurabh

  • Sorrowfull Blinger

    Awesome blog ! Love it ! really helpful

  • Amit Dutta

    Hi
    The post is great. I have a query: What if we change the input matrix after pre-computation step? Do we need to run the pre-processing over the whole matrix again? Or there is a easy step to incorporate changes in input matrix even after pre computation?

    • Saurabh

      Amit,
      Of course we have to recompute again. Think about it. When you change a value in a block X , the addition for OX as well as for every block that is beyond the block X, or in other words, addition for all the matrices which have OX inside them will change. If you don’t know which blocks and how many blocks will change with what frequency then you can do nothing, you have to run the pre-computation step every time the value changes. May be you can only compute the sum for OX and the blocks which are beyond OX, that will save the time to compute the additions of the blocks which have not changed.

      Saurabh

  • shru

    does this solution work for all cases ? what happens when first index > second index?