Start learning free

LESSON 240 OF 414 · PARTIAL SUMS #2

Maximum Sum Submatrix in Scala: 2D Prefix Sums in O(m^2 * n^2)

Practice O(n2 * m2) 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 17
    Ctrl + Enter to check

    SCALA · PARTIAL SUMS #2

    Maximum Sum Submatrix in Scala, explained

    Problem overview

    The method maxSum receives an Array[Array[Int]] called grid, an m x n grid of integers that may be positive, negative or zero. It returns the largest sum that any rectangular block of cells, a submatrix, can have. A single cell counts as a submatrix.

    In the example grid

    [ 1,  -9, -10,  1]
[-1,  10,  10,  1]
[ 0,   9,   9, -9]
[-1,  -1,  -1, -1]

    the best submatrix is the block [[10, 10], [9, 9]] in the middle, with sum 38.

    Approach: sum any rectangle in constant time

    A submatrix is fixed by two corners: the top-left cell (x1, y1) and the bottom-right cell (x2, y2). Looping over all pairs of corners is simple. The costly part would be adding up the cells of each rectangle, which can take up to m * n steps and would make the whole search far too slow.

    The fix is a table of 2D prefix sums. Entry partialSums(i)(j) holds the sum of the rectangle that runs from (0, 0) to (i, j). It is built in one pass with inclusion-exclusion: the entry is the cell itself, plus the entry above it, plus the entry to its left, minus the entry diagonally above-left, which the two neighbours both include.

    For the example grid the table is:

    1  -8 -18 -17
0   1   1   3
0  10  19  12
-1  8  16   8

    With the table, the sum of any rectangle takes four lookups, again by inclusion-exclusion. Start from the big rectangle that ends 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)

    Here P is the prefix table, and any entry with a negative index counts as 0. For the middle block, (x1, y1) = (1, 1) and (x2, y2) = (2, 2), so the sum is 19 - (-18) - 0 + 1 = 38.

    The search still tries every pair of corners, which is about m^2 * n^2 / 4 rectangles. Each now costs O(1), so the total is O(m^2 * n^2). A later lesson on this problem improves on it.

    Step by step

    1. Create result as a var holding grid(0)(0). A single cell is a submatrix, so this is a sum that really exists, even when every number is negative.
    2. Create partialSums as a val with a nested Array.fill: grid.length rows, each one an Array.fill of grid(0).length zeros. The inner Array.fill runs once per row, so each row is its own array.
    3. Loop i over the rows, from 0 until grid.length.
    4. Loop j over the columns inside it, from 0 until grid(0).length.
    5. Write the helper get, placed above maxSum. It takes a grid, a row i and a column j, and returns the value there, or 0 when the position is outside the grid. This lets the formulas look one row up or one column left without special cases at the edges.
    6. Inside get, an if checks that both indices are at least 0 and below the sizes, and returns grid(i)(j). After the if, the last expression is 0.
    7. Fill the table. In the j loop, set partialSums(i)(j) to the cell, plus get(partialSums, i - 1, j), plus get(partialSums, i, j - 1), minus get(partialSums, i - 1, j - 1).
    8. Choose the top-left corner with loops x1 over the rows and y1 over the columns.
    9. Choose the bottom-right corner inside them: x2 from x1 until the number of rows, and y2 from y1 until the number of columns. The bottom can't be above the top and the right side can't be left of the left side.
    10. Compute sum as a val with the four-lookup formula, reading through get so that corners on the top or left edge work.
    11. Update result with math.max(result, sum).
    12. End with result as the last expression of maxSum.

    The solution in Scala

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

    def maxSum(grid: Array[Array[Int]]): Int = {
        var result = grid(0)(0)
        val partialSums = Array.fill(grid.length)(Array.fill(grid(0).length)(0))

        for (i <- 0 until grid.length) {
            for (j <- 0 until grid(0).length) {
                partialSums(i)(j) = grid(i)(j) + get(partialSums, i - 1, j) +
                get(partialSums, i, j - 1) -
                get(partialSums, i - 1, j - 1)
            }
        }

        for (x1 <- 0 until grid.length) {
            for (y1 <- 0 until grid(0).length) {
                for (x2 <- x1 until grid.length) {
                    for (y2 <- y1 until grid(0).length) {
                        val sum = get(partialSums, x2, y2) -
                        get(partialSums, x1 - 1, y2) -
                        get(partialSums, x2, y1 - 1) +
                        get(partialSums, x1 - 1, y1 - 1)
                        result = math.max(result, sum)
                    }
                }
            }
        }
        result
    }
}

    The Scala details worth knowing:

    • A grid is an array of arrays. grid(i)(j) is the cell in row i and column j. The number of rows is grid.length and the number of columns is grid(0).length.
    • Array.fill(rows)(Array.fill(cols)(0)). The value in the second parentheses is evaluated again for every element, so each row is a separate array. Writing one cell, as in partialSums(0)(0) = 1, changes that row only. Reusing one array object for all the rows would make the rows share their cells.
    • Line breaks inside an expression. A line that ends with + or - clearly continues on the next line, which is how the long formulas in the solution are split. Ending each broken line with its operator is also the safest style, since it is read the same way in any version of Scala.
    • Mutating a val array. partialSums is a val, but its elements can still be assigned, because the array is mutable. The val only fixes which array the name points to.
    • return in get leaves the method early. The final 0 is the value when the if doesn't apply, because the last expression is the method's result.

    Complexity

    Let the grid have m rows and n columns.

    Time: O(m^2 * n^2). Building the table is O(m * n). The four nested loops then visit every pair of corners, and each rectangle sum is a constant number of lookups.

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

    Edge cases and common mistakes

    • All numbers negative. [[-3, -1], [-2, -4]] gives -1, the best single cell. Starting result at 0 would wrongly return 0.
    • One cell. [[5]] gives 5.
    • All numbers positive. The whole grid is the best submatrix. For [[1, 2], [3, 4]] the answer is 10.
    • Rectangles on the top or left edge. For them x1 - 1 or y1 - 1 is -1. The helper turns those lookups into 0, so no special cases are needed.
    • Forgetting the added-back corner. Without + get(partialSums, x1 - 1, y1 - 1) the region above and to the left is subtracted twice, and the sum is too small.
    • Starting x2 at 0. A bottom row above the top row would describe a rectangle that doesn't exist, and the formula would give a meaningless number.

    Testing

    • The example grid above gives 38.
    • [[-3, -1], [-2, -4]] gives -1.
    • [[5]] gives 5.
    • [[1, 2], [3, 4]] gives 10.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free