LESSON 217 OF 348 · PARTIAL SUMS #2

Maximum Sum Submatrix in Kotlin: 2D Prefix Sums, O(m²n²)

Practice O(n² * m²) Read the full explanation

Given a m x n grid filled with integers, find the submatrix with maximum sum among all submatrices.

Example:

Input:
[
  [ 1,  -9, -10,  1],
  [-1,  10,  10,  1],
  [ 0,   9,   9, -9],
  [-1,  -1,  -1, -1]
]
Output: 38
Explanation: Submatrix [[10, 10], [9, 9]]

STEP 1 OF 14

Guided

Ctrl + Enter to check

KOTLIN · PARTIAL SUMS #2

Maximum Sum Submatrix in Kotlin, explained

Problem overview

The function maxSum receives a grid of integers, an Array<IntArray> with m rows and n columns. A submatrix is a rectangle of adjacent rows and columns. The function returns the largest sum of any submatrix. The grid may contain negative numbers.

In the example the grid is:

 1  -9 -10   1
-1  10  10   1
 0   9   9  -9
-1  -1  -1  -1

The submatrix [[10, 10], [9, 9]] sums to 38, and no other rectangle comes close, so the answer is 38.

Approach: a 2D table of prefix sums

A grid with m rows and n columns has about m²n²/4 submatrices. Adding up each one cell by cell would add another factor of up to m * n. The goal is to make the sum of any submatrix cost a constant number of operations.

The tool is a table of partial sums. Let partialSums[i][j] be the sum of the rectangle from the top-left cell (0, 0) to (i, j). It can be built from its neighbours:

partialSums[i][j] = grid[i][j] + partialSums[i-1][j] + partialSums[i][j-1] - partialSums[i-1][j-1]

The rectangle above the cell and the rectangle to its left both contain the rectangle diagonally up and to the left, so that one has been counted twice and is subtracted once.

With that table, the sum of any submatrix with top-left corner (x1, y1) and bottom-right corner (x2, y2) comes from the same inclusion-exclusion idea in reverse. Take the big rectangle ending at (x2, y2), remove the rows above the submatrix and the columns to its left, and add back the corner that was removed twice:

sum = P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]

Check it on the example. The submatrix from (1, 1) to (2, 2) needs four table values: P[2][2] = 19, P[0][2] = -18, P[2][0] = 0 and P[0][0] = 1. The sum is 19 - (-18) - 0 + 1 = 38.

The solution then tries every pair of corners, with the bottom-right corner never above or left of the top-left one, and keeps the best sum. That is four nested loops with a constant-time body.

Step by step

Declare result with var, starting at grid[0][0]. A single cell is a submatrix, so this value is safe even when every number is negative. Starting at 0 would be wrong in that case.
Declare partialSums with val, as Array(grid.size) { IntArray(grid[0].size) }. The lambda builds a separate zero-filled row for each of the rows. The cells can still change, even though the name is a val.
Loop i over the rows and, inside it, loop j over the columns, to visit every cell.
Write the helper get. It takes a grid, a row and a column, and returns the value there, or 0 if the position is outside the grid. Declare it above maxSum.
Give it the bounds test. If both coordinates are at least 0 and below the row and column counts, return grid[i][j]. After the if, return 0.
Build the table. Inside the j loop, set partialSums[i][j] to the cell plus the sum above it, plus the sum to its left, minus the sum diagonally up and left. Reading the neighbours through get turns anything outside the grid into 0, so the first row and column need no special code.
Choose the top-left corner. Loop x1 over the rows, and inside it loop y1 over the columns.
Choose the bottom-right corner. Inside the y1 loop, loop x2 from x1 to the last row, and inside that, y2 from y1 to the last column. The bottom row can't be above the top row, and the right column can't be left of the left column.
Compute the submatrix sum into a val named sum with the four-term formula, again through get. When x1 or y1 is 0, the terms that would be outside the table become 0.
Update result with maxOf(result, sum).
Return result after all the loops.

The solution in Kotlin

class Solution {
    fun get(grid: Array<IntArray>, i: Int, j: Int): Int {
        if (i >= 0 && i < grid.size && j >= 0 && j < grid[0].size) {
            return grid[i][j]
        }
        return 0
    }

    fun maxSum(grid: Array<IntArray>): Int {
        var result = grid[0][0]
        val partialSums = Array(grid.size) { IntArray(grid[0].size) }

        for (i in 0 until grid.size) {
            for (j in 0 until grid[0].size) {
                partialSums[i][j] = grid[i][j] + get(partialSums, i - 1, j) +
                get(partialSums, i, j - 1) -
                get(partialSums, i - 1, j - 1)
            }
        }

        for (x1 in 0 until grid.size) {
            for (y1 in 0 until grid[0].size) {
                for (x2 in x1 until grid.size) {
                    for (y2 in y1 until grid[0].size) {
                        val sum = get(partialSums, x2, y2) -
                        get(partialSums, x1 - 1, y2) -
                        get(partialSums, x2, y1 - 1) +
                        get(partialSums, x1 - 1, y1 - 1)
                        result = maxOf(result, sum)
                    }
                }
            }
        }
        return result
    }
}

The Kotlin details worth a closer look:

Where a line may break. The long expressions are split so that each broken line ends with + or -. Kotlin ends a statement at the end of a line unless the expression is clearly unfinished, and a trailing operator means more is coming. If the operators began the next lines instead, each would be read as a separate statement, a unary plus or minus, and the value assigned would be only the first line. With a = 10, b = 4 and c = 3, writing the operators at the start of the lines leaves 10 instead of 11.
A grid is an array of arrays. Array<IntArray> is an Array whose elements are IntArrays, and grid[i][j] reads the row first, then the column. The table is created with the lambda form Array(size) { ... } so that each row is a separate array. A single shared row would make every row alias the same data.
Member function named get. It is an ordinary method here, called as get(partialSums, i - 1, j). It takes the table as its grid parameter, so the same helper reads both the input and the prefix table.
Arrays are references. Passing partialSums to get doesn't copy it. The helper only reads from it.
until grid.size and grid.indices. 0 until grid.size and grid.indices mean the same range. The lesson spells it out.

Complexity

Let the grid have m rows and n columns.

Time: O(m²n²). Building the table visits each cell once, which is O(m * n). The four loops then visit every pair of corners, and each pair costs a constant number of lookups. The number of pairs is about m²n²/4, so the loops dominate the running time. Without the table, each sum would cost up to O(m * n) more.

Space: O(m * n). The table partialSums has as many cells as the grid.

Edge cases and common mistakes

All negative numbers. For [[-3, -1], [-2, -4]] the answer is -1, the best single cell. Starting result at 0 would report 0, the sum of an empty rectangle.
A single cell. A grid of one number returns that number: [[5]] gives 5.
Submatrices touching the top or left border. These are the cases that need get to return 0 for row -1 or column -1. Reading partialSums[-1][...] directly would throw an ArrayIndexOutOfBoundsException.
Forgetting the added corner. Without the last term, the region above and to the left of the submatrix is subtracted twice. The sum is wrong whenever that region's total isn't 0.
Starting x2 at 0 or y2 at 0. A bottom-right corner above or left of the top-left one doesn't describe a rectangle, and the formula would produce meaningless sums.
An empty grid. grid[0][0] throws an exception, so the function expects at least one cell.
Overflow. Prefix sums are Int values and wrap silently if the grid's total passes about 2.1 billion.

Testing

The grid from the example gives 38.
[[-3, -1], [-2, -4]] gives -1.
[[5]] gives 5.
[[-2, 3, -1], [4, -5, 6]] gives 6.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free