Matrix region sum
Given a matrix of integers and coordinates of a rectangular region within a matrix find the sum of numbers falling inside the rectangle.
Step 1: Questions
Q: Will this operation be called repeatedly?
A: Yes.
Step 2: Design an algorithm
The naive approach is to compute the sum of all numbers falling within the specified region every time the function is called:
But this runs O(MN) every time it is called. We still have to get through all the numbers to compute the sum, but since this operation is done multiple times then perhaps we can create a cache by calculating the sums of all matrices starting at the origin (0,0) and ending at every possible cell in the matrix. Although this will be a one time preprocessing procedure we can still optimize it to avoid spending O((MN)^2) time. If we cache our findings as we scan the matrix, then we can rely on the sum of the north, west and northwest cells to compute the sum of the current cell given this formula (a little dynamic programming):
sum at west cell + sum at north cell — sum at northwest cell + number at this cellWhat I mean is this:
There were two bugs that I had in the initial version of the code and fixed in the code you see above.
- When I was looking up coordinates in the cache I was using new Coordinate(x , y) as the key. If you do not override hashCode() and equals() methods in your Coordinate class definition, then the cache will never be able to get the coordinate you need, because it will be looking for the exact object that you put in there, which is long gone, and know nothing of the new object you create even though it has the same x,y coordinates.
- In an NxN matrix the user will pass in coordinates, where the origin is (0,0) and bottom-right is (3,3). I forgot to accommodate for that which resulted in getting the answer for a NullPointerException.
The code above runs in O(MN) time now.
**This question comes from ‘28 interview questions’ by Arden Dertat
