Press "Enter" to skip to content

How To Find The Sum Of Numbers In A Rectangular Region In A Matrix

Ajk 0

Given a matrix of ints and a rectangular region inside the matrix, find the sum of all the numbers within the rectangle.

This is a very good interview question that will show your interviewer a lot about the way you think. It seems easy to solve at first but, as per usual, your first solution might not be the most efficient one.

Unlike other problems, with this one we’ll leave the clarifications for later and jump straight into code. After all it seems pretty straight forward. We just have to go through each item in the rectangle and sum it up.

How Find The Sum Of Numbers In A Rectangular Region In A Matrix – Standard

Easy enough no?

Notes:

  • We assume we are given a non null matrix with at least one element.
  • We assume the rectangle is within the given matrix
  • Bottom line, we make a bunch of assumptions for which we have to get a confirmation from our code (or our interviewer in this case), or otherwise we have to get appropriate checks. A quick analysis of the complexity will show an O(n) time complexity (where n is the number of elements in the rectangle. Auxiliary space is O(1) (emphasis on auxiliary, as we have the whole matrix array as an input already).

    Good, good but is it good enough? We walk around the room, scratch our head a bit and don’t think we can get the sum without going through each and every single element in the rectangle, therefore we should have the best solution. And then our interviewer (or code) hints us that we will probably have to call this method many many times and not only once.

    At this point we think that maybe we will have to cache our rectangles. After that we could simply But which ones? Storing all possible rectangles in memory will take O(m2n2). Not a good trade off. Turns out that we can calculate every other rectangle from the rectangles starting from 0 and ending at each point in the matrix. Any rectangle with vertices A, B, C, D can be calculated by the simple formula:

    • Rectangle(PointA, PointD) = Rectangle(Point0, PointA) + Rectangle(Point0, PointD) – Rectangle(Point0, PointB) – Rectangle(Point0, PointC)

    Let’s head right into code!

    How To Find The Sum Of Numbers In A Rectangular Region In A Matrix – By Cache

    Keep in mind that we will call the first method ComputeMatrixSubSums only once! And the our final computation will now take only O(1) time!!

    Finding the sum of numbers in a rectangular region in a matrix is a great question because all in all, you can now say you build a dynamic algorithm (which in cheap words is – computing results from cached pre-computations).

    As always you can find the full code in my GitHub Interview Questions repo.
    Hope you guys enjoyed it… and I’ll see you guys next time ;D

    The following two tabs change content below.
    If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂