LESSON 218 OF 348 · PARTIAL SUMS #2

Maximum Sum Submatrix in Kotlin: Column Sums and Kadane in O(n²m)

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 n rows and m columns. It returns the largest sum of any submatrix, which is a rectangle of adjacent rows and columns. The numbers can be negative.

In the example the grid is:

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

The best rectangle is [[10, 10], [9, 9]], with sum 38.

Approach: fix two rows, then solve a one-dimensional problem

The other lesson on this problem tries every pair of corners, which needs four nested loops. This version fixes only the top and bottom rows, x1 and x2, and gets rid of two of the loops.

Once the two rows are fixed, a submatrix is a choice of a left and a right column. Add up each column between the two rows and put the results in an array nums of length m. A submatrix between those rows now corresponds to a contiguous subarray of nums, and its sum is the subarray's sum. The best submatrix between the two rows is therefore the maximum subarray sum of nums, a problem with a linear-time solution.

The column sums for every pair of rows come from a table of running totals down each column. columnPartialSums[i][j] is the sum of column j from row 0 to row i. The sum of column j between rows x1 and x2 is columnPartialSums[x2][j] minus columnPartialSums[x1 - 1][j], and the second term is left out when x1 is 0.

Take the rows x1 = 1 and x2 = 2 in the example. The column sums are -1 + 0, 10 + 9, 10 + 9 and 1 + (-9), so nums = [-1, 19, 19, -8]. The best subarray is [19, 19], with sum 38, which matches the expected answer.

Step by step

Store the dimensions. Put grid.size in n and grid[0].size in m, both with val.
Declare result with var, starting at grid[0][0]. A single cell is a submatrix, so this is a safe starting value, even if the answer is negative.
Create columnPartialSums with val, as Array(n) { IntArray(m) }.
Fill it with two nested loops, i over the rows and j over the columns. Set each cell to grid[i][j].
Add the total above. If i is greater than 0, add columnPartialSums[i - 1][j] to the cell. Row 0 has nothing above it.
Choose the top row. Loop x1 over all rows.
Choose the bottom row. Inside it, loop x2 from x1 to the last row, since the bottom can't be above the top.
Create nums as a val holding an IntArray(m). It receives the column sums between the two rows.
Loop y over the columns.
Start from the total down to the bottom row. Set nums[y] to columnPartialSums[x2][y].
Cut off the part above the top row. If x1 is greater than 0, subtract columnPartialSums[x1 - 1][y] from nums[y]. What remains is the sum of rows x1 to x2.
Solve the one-dimensional problem. Call maxSumSubarray(nums), store the value in a val named sum, and update result with maxOf(result, sum).
Return result after the loops.
Implement maxSumSubarray above maxSum. It keeps result, the best sum so far, starting at nums[0], and maxSum, the best sum of a subarray that ends at the current element, starting at 0. For each value, set maxSum to value + maxOf(maxSum, 0), then update result with maxOf(result, maxSum).

The helper uses Kadane's idea. A subarray that ends just before value and has a negative sum can only make the next subarray worse, so it is dropped by replacing it with 0 before value is added. A subarray that has a positive sum is kept and extended.

The solution in Kotlin

class Solution {
    fun maxSumSubarray(nums: IntArray): Int {
        var result = nums[0]
        var maxSum = 0
        for (value in nums) {
            maxSum = value + maxOf(maxSum, 0)
            result = maxOf(result, maxSum)
        }
        return result
    }

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

        val columnPartialSums = Array(n) { IntArray(m) }
        for (i in 0 until n) {
            for (j in 0 until m) {
                columnPartialSums[i][j] = grid[i][j]
                if (i > 0) {
                    columnPartialSums[i][j] += columnPartialSums[i - 1][j]
                }
            }
        }

        for (x1 in 0 until n) {
            for (x2 in x1 until n) {
                val nums = IntArray(m)
                for (y in 0 until m) {
                    nums[y] = columnPartialSums[x2][y]
                    if (x1 > 0) {
                        nums[y] -= columnPartialSums[x1 - 1][y]
                    }
                }
                val sum = maxSumSubarray(nums)
                result = maxOf(result, sum)
            }
        }
        return result
    }
}

The Kotlin details worth a closer look:

Two functions in one class. maxSumSubarray and maxSum are both members of Solution. Inside maxSum, the call maxSumSubarray(nums) needs no receiver; it calls the method on the same object. Kotlin doesn't require a function to be declared before its use inside a class.
Same names, different scopes. Both functions have a local result, and maxSumSubarray also has a maxSum variable whose name matches the other function. A local variable and a method live in different namespaces, so this is legal, though it reads confusingly. They never interfere.
Compound assignment on array cells. columnPartialSums[i][j] += columnPartialSums[i - 1][j] reads the cell, adds, and writes it back. -= works the same way for nums[y].
val with a mutable array. val nums = IntArray(m) fixes which array the name refers to; its elements are still assigned in the loop. A fresh nums is created for each pair of rows, so no values carry over.
Array(n) { IntArray(m) }. The lambda runs once per row and creates a separate zero-filled row each time.

Complexity

Time: O(n² * m). Building the column table takes O(n * m). There are about n²/2 pairs of rows, and for each pair the function fills nums in O(m) and runs the linear subarray scan over it, also O(m). That is an improvement of a factor of about m over the four-loop version, which takes O(n² * m²).

Space: O(n * m). The column table has as many cells as the grid, and nums adds O(m).

Edge cases and common mistakes

All negative numbers. For [[-3, -1], [-2, -4]] the answer is -1. The helper starts result at nums[0], and the reset to 0 happens before adding value, so a subarray is never empty.
A single cell or a single row. [[5]] returns 5. With one row, x1 and x2 are both 0, and the problem is the one-dimensional one.
Forgetting the x1 > 0 check. Reading columnPartialSums[-1][y] throws an ArrayIndexOutOfBoundsException.
Not subtracting the part above the top row. The column sums would then include rows above x1 and the results would be too large or too small, depending on the signs.
Using 0 as the helper's starting best. A start of 0 would report 0 for an all-negative row, which isn't the sum of any non-empty subarray.

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