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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 
/* * @Author: Ajk Palikuqi * * @Question: How To Find The Sum Of Numbers In A Rectangular Region In A Matrix */ package iqLib.arrayLib; import java.awt.Point; import java.util.Arrays; public class MatrixSubSum { public static int FindMatrixSubSum1(int[][] nMatrix, Point nTopLeft, Point nBottomRight) { int nSum = 0; for (int i = nTopLeft.x; i < nBottomRight.x; ++i) { for (int j = nTopLeft.y; j < nBottomRight.y; ++j) { nSum += nMatrix[i][j]; } } return nSum; } } 
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(m^{2}n^{2}). 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(Point_{A}, Point_{D}) = Rectangle(Point_{0}, Point_{A}) + Rectangle(Point_{0}, Point_{D}) – Rectangle(Point_{0}, Point_{B}) – Rectangle(Point_{0}, Point_{C})
Let’s head right into code!
How To Find The Sum Of Numbers In A Rectangular Region In A Matrix – By Cache
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960/** @Author: Ajk Palikuqi** @Question: How To Find The Sum Of Numbers In A Rectangular Region In A Matrix*/package iqLib.arrayLib;import java.awt.Point;import java.util.Arrays;public class MatrixSubSum{public static int[][] ComputeMatrixSubSums(int[][] nMatrix){int nRows = nMatrix.length;int nColumns = nMatrix[0].length;//Shows the computed sums of the rectangle from point 0,0 to here inclusive.int nComputedSums[][] = new int[nRows][nColumns];//Compute sums for the firt row and first columnnComputedSums[0][0] = nMatrix[0][0];for (int j = 1; j < nColumns; ++j){nComputedSums[0][j] = nComputedSums[0][j1] + nMatrix[0][j];}for (int i = 1; i < nRows; ++i){nComputedSums[i][0] = nComputedSums[i1][0] +nMatrix[i][0];}//Compute sums for the restfor (int i = 1; i < nRows; ++i){for (int j = 1; j < nColumns; ++j){nComputedSums[i][j] = nComputedSums[i][j1] + nComputedSums[i1][j] nComputedSums[i1][j1] + nMatrix[i][j];}}return nComputedSums;}public static int FindMatrixSubSumByCache(int[][] nMatrix, Point nTopLeft, Point nBottomRight, int[][] computedSums){int nSum = 0;for (int i = nTopLeft.x; i < nBottomRight.x; ++i){for (int j = nTopLeft.y; j < nBottomRight.y; ++j){nSum += nMatrix[i][j];}}return nSum;}}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 precomputations).
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 ;DThe 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 ðŸ™‚Latest posts by Ajk (see all)
 Find Median from Numbers Array  January 1, 2018
 Find Whether a Number Can Be the Sum of Two Squares  August 12, 2017
 How to Find Two Primes Whose Sum is Equal to a Number N  April 22, 2017