Problem overview
The method maxSum receives a rectangular grid of integers, as a number[][]. Among all submatrices (rectangles of adjacent rows and columns, at least one cell), it returns the largest sum.
In the example grid
[ 1, -9, -10, 1]
[-1, 10, 10, 1]
[ 0, 9, 9, -9]
[-1, -1, -1, -1]
the best rectangle is [[10, 10], [9, 9]] in the middle, which sums to 38.
Approach: a table of sums from the corner
A submatrix is fixed by two corners: top-left (x1, y1) and bottom-right (x2, y2). The number of such pairs is about R² * C² for R rows and C columns. If each rectangle's sum had to be added cell by cell, the total would be higher still. The goal of this lesson is to make each rectangle sum cost O(1).
The tool is a 2D prefix sum table. Let partialSums[i][j] be the sum of the rectangle from (0, 0) to (i, j). It can be built from three neighbours with inclusion-exclusion: the cell itself, plus the table value above, plus the table value to the left, minus the table value diagonally up-left, which the two previous ones both include.
The same idea runs backwards for any rectangle. Take the big prefix rectangle that ends at the bottom-right corner, subtract the part above the top row and the part left of the left column, and add back the corner that was subtracted twice:
sum = P(x2, y2) - P(x1 - 1, y2) - P(x2, y1 - 1) + P(x1 - 1, y1 - 1)
On the example grid, the prefix table gives P(2, 2) = 19, P(0, 2) = -18, P(2, 0) = 0 and P(0, 0) = 1. The rectangle from (1, 1) to (2, 2) is 19 - (-18) - 0 + 1 = 38, as expected.
Prefix values at an index of -1 (above the first row or left of the first column) are 0, because nothing lies there. A helper method get returns 0 for out-of-range positions so the formulas don't need special cases.
Step by step
- Start
resultatgrid[0][0]. A single cell is a submatrix, so this is a real sum. Starting at 0 would be wrong when every cell is negative. - Create
partialSumsas an emptynumber[][]. For each row ofgrid, push a new array ofgrid[0].lengthzeros made withfill(0). Each row has to be its own array. - Loop over rows with
iand, inside, over columns withj, to visit every cell. - Write
get(grid, i, j). It checks that both indices are inside the grid and returns that cell, and otherwise returns 0. - Fill the table.
partialSums[i][j]isgrid[i][j]plusgetof the cell above, plusgetof the cell to the left, minusgetof the cell diagonally up-left. Becausegetreturns 0 outside the table, the first row and column need no special code. - Choose the top-left corner with
x1over rows andy1over columns. - Choose the bottom-right corner with
x2fromx1andy2fromy1. The bottom can't be above the top, and the right side can't be left of the left side. - Compute the rectangle's sum with the four-term formula above, using
getonpartialSums. - Keep the maximum with
Math.max(result, sum), then returnresultafter the loops.
The solution in TypeScript
class Solution {
get(grid: number[][], i: number, j: number): number {
if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
return grid[i][j];
}
return 0;
}
maxSum(grid: number[][]): number {
let result = grid[0][0];
let partialSums: number[][] = [];
for (let i = 0; i < grid.length; ++i) {
partialSums.push(new Array(grid[0].length).fill(0));
}
for (let i = 0; i < grid.length; ++i) {
for (let j = 0; j < grid[0].length; ++j) {
partialSums[i][j] = grid[i][j] + this.get(partialSums, i - 1, j) +
this.get(partialSums, i, j - 1) -
this.get(partialSums, i - 1, j - 1);
}
}
for (let x1 = 0; x1 < grid.length; ++x1) {
for (let y1 = 0; y1 < grid[0].length; ++y1) {
for (let x2 = x1; x2 < grid.length; ++x2) {
for (let y2 = y1; y2 < grid[0].length; ++y2) {
let sum = this.get(partialSums, x2, y2) -
this.get(partialSums, x1 - 1, y2) -
this.get(partialSums, x2, y1 - 1) +
this.get(partialSums, x1 - 1, y1 - 1);
result = Math.max(result, sum);
}
}
}
}
return result;
}
}
Some TypeScript details:
- Calling a method from a method.
getis a method of the class, so insidemaxSumit must be called asthis.get(...). Writing plainget(...)would look for a variable or function of that name and fail. Note thatgetis also a contextual keyword for accessors in classes, but as a method name followed by parentheses it is an ordinary name. - Two-dimensional arrays are arrays of arrays. Each row of
partialSumsis a separate array. That is why the code pushes a newArray(...).fill(0)per row. Filling a single row array and pushing the same one repeatedly would make every row share the same storage. - Continuing an expression across lines. The statement that sets
partialSums[i][j]ends with the semicolon after the last term, not at the first line break, so a long formula can be split over lines. Each line break comes after an operator, which makes it clear the expression goes on. - Annotations are erased. The
number[][]types are checked by the compiler and disappear from the JavaScript.
Complexity
Let the grid have R rows and C columns.
Time: O(R² * C²). Building the table takes O(R * C). The four nested loops then visit every pair of corners, about R² * C² / 4 of them, and each rectangle costs a constant number of lookups. Without the table, every rectangle would need its own summing loop.
Space: O(R * C). The table partialSums has the same shape as the grid.
Edge cases and common mistakes
- All negative. For
[[-3, -1], [-2, -5]]the answer is-1, the single best cell. - One cell.
[[5]]gives5. - One row or one column.
[[1, 2, 3]]gives6, and[[1], [-5], [4]]gives4. - Not adding the corner back. The formula subtracts the top-left region twice unless you add
P(x1 - 1, y1 - 1)once. - Rectangles touching the edge. When
x1ory1is 0, the index-1is read. That is safe only becausegetreturns 0 for it. ReadingpartialSums[-1]directly would giveundefinedand then an error. - An empty grid.
grid[0][0]would throw on[]. The lesson's grids always have at least one cell.
Testing
- The grid from the example gives
38. [[-3, -1], [-2, -5]]gives-1.[[1, 2, 3]]gives6.[[2, -1], [-1, 2]]gives2.[[1, 1], [1, 1]]gives4.