Beating AlgoExpert: Maximum Sum Submatrix
Welcome back to Beating AlgoExpert, a series of articles showing how to surpass the experts best solutions. You can see the previous article in this series here.
Today’s problem is titled Maximum Sum Submatrix and can be found on AlgoExpert here. Unfortunately, I could not find this problem on Leetcode nor HackerRank so I apologize to readers who do not have access.
The Prompt
Given a two dimensional matrix, our goal is to find the largest submatrix of of width and height both equal to size. It is guaranteed that the matrix width and height will both be greater than or equal to size, and size will be a positive integer.
For example…
How AlgoExpert Solves the Problem
The first step is to build an array of running sum so that at any row and col vertices, you would have the sum of the values whose point lies within the contained in the rows and columns within that vertex.
If we look at row index 1 and column index 1 in our running sum matrix, we get a running sum of 4, which is what we would get if we added all numbers to the left and above that vertex (5+3+(-7)+3). This calculation costs us a run time of O(n) and a space complexity of O(n).
Once that is calculated you can start at the vertex(size-1, size-1) and run through the matrix calculating the size of the square by removing any area above the square, any area to the left of the square and adding back overlapping areas. Remember that all areas are represented by their lower right vertex in the running sum matrix. Let’s look at the middle square calculation
To calculate the blue square, we can take the sum of the whole area represented by the purple box which we know is 30, we then subtract the area above (orange box) which is 7 and the area to the left (red box) which is 10. Doing this subtracts one area twice as there is some overlap represented by the green box at 5, we then add that back in and get a total of 30–7–10+5 = 18. This is validated by looking at the original grid and if we add 3, 7, 8, and 0, we also get 18.
All that is left to track the max and voila, a very simple and elegant solution. But as mentioned it does require a space complexity of O(n) and I will show you how to beat that, additionally we will solve the problem in one single run through.
Approaching The Problem
Imagine an array of size n, and you need to find the largest sum of k consecutive numbers. We could approach the problem by building the running sum array then each index at i ≥ k would be the running sum at index i less the running sum at index i-k, but it would also be just as easy to add the next number and drop the last in our first run through, not creating the excess array. For example given the array below with size k = 3:
We could continue this pattern to the end and have our solution easy. This will be the basis for the solution. We add all the values in the next square and subtract all the ones we lost.
First, as you may have noticed, we need to calculate the sum of the vertical numbers we are adding, and with a large size, that creates a large calculation. Second, once we reached the end of the row and want to start on the next row, we calculate a whole new box. We can account for both of these obstacles
First, calculating the the vertical sums. We create an array of the same width as the matrix, filled with zeros. Let’s call this array verticalSums. As we iterate through the matrix, we add the value to its corresponding vertical index in verticalSums. If the row index is greater than or equal to size, we can then subtract the vertex that is size places above it. We then will have the corresponding vertical sums we need to add or subtract. Below we can see what this array looks like after iterating through each row.
We only have access to one version of the array at a time, once we start iterating through a new row, the values get replaced. That is okay, once we are on the next row, we don’t need to know the previous vertical sums anymore.
Author’s Note: I am also leveraging a Just In Time model for calculating the vertical sum, a methodology made popular in factory physics via Lean Production and the Toyota Production System. Highly recommend you look into it! Using other resources to guide the design and development process is always beneficial.
Next we need to keep track of the horizontal sums. Again we use an array with length to the matrix height, we call this array horizontalSums. For this array we are not completely replacing through each row as we only need the initial horizontal sums. As we iterate through the matrix, if the vertical index is less than size, we add the value to the corresponding row index of our horizontalSums array. We end up with this final horizontalSums array.
We can then use a running sum variable, called startRowSum, to track our starting sum for each row, similar how we approached the array at the beginning of this section.
Lastly we will use two additional variables, our max which will be the max sum that we have seen while iterating through and a currentSum which is the calculation of our the area we need to know. Every time we start a new row in our iteration process, we reset our currentSum variable to the startRowSum then add and subtract the corresponding vertical sum from our verticalSums array. At every new calculation of currentSum, we compare it to max and update it if needed.
Putting the Code Together
The final code seen below is my solution. By using tracking variables verticalSums and horizontalSums, we are able to achieve a space complexity at O(w+h) where w is the width of the matrix and h is the height of the matrix. Additionally we are only iterating through the matrix in one pass, which does not guarantee that it is more efficient but it is pretty dang cool.
Please add any comments if you enjoyed this read or if you wish to discuss this solution in more details. Thanks for reading.
