Start learning free

LESSON 216 OF 338 · PARTIAL SUMS #2

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

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 14
    Ctrl + Enter to check

    GO · PARTIAL SUMS #2

    Maximum Sum Submatrix in Go, explained

    Problem overview

    The method maxSum receives a grid of integers, a [][]int with m rows and n columns. It returns the largest sum over all submatrices: rectangles of adjacent rows and columns. The numbers may be negative.

    In the example grid, the submatrix made of the rows 1 and 2 and the columns 1 and 2 holds 10, 10, 9 and 9, which add up to 38. No other rectangle does better, so the answer is 38.

    Approach: prefix sums on a grid

    A submatrix is fixed by its top-left corner (x1, y1) and its bottom-right corner (x2, y2). There are about m²n²/4 such pairs, so trying all of them is only feasible if each rectangle's sum costs O(1). Adding up the cells one by one would multiply the cost by the area.

    The 2D prefix sum gives the constant-time sum. Let partialSums[i][j] be the sum of the rectangle from (0, 0) to (i, j). It is built by inclusion and exclusion: the cell itself, plus the rectangle above, plus the rectangle to the left, minus the rectangle above-left, which the previous two both include. Any rectangle's sum is then the same trick run backwards: the big prefix rectangle, minus the rows above, minus the columns to the left, plus the corner that was subtracted twice.

    Step by step

    1. Start result at grid[0][0]. A single cell is a submatrix, so this is a safe start even when everything is negative.
    2. Allocate partialSums. Make a [][]int with len(grid) rows, then make each row a slice of len(grid[0]) zeros. make([][]int, n) alone leaves every row nil, so each row must be made before it is written.
    3. Loop over rows i and columns j to fill the table.
    4. Write the helper get. It is a method on Solution that returns the value at (i, j), or 0 when the position is outside the grid. Then the formulas can look one row up or one column left without special cases for the first row and column.
    5. Use a bounds check. If i and j are both at least 0 and below the row and column counts, return grid[i][j]; otherwise return 0.
    6. Fill each prefix cell as grid[i][j] plus get(i-1, j) plus get(i, j-1) minus get(i-1, j-1).
    7. Choose the top-left corner with the loops x1 over rows and y1 over columns.
    8. Choose the bottom-right corner with x2 from x1 and y2 from y1, so the rectangle is never inverted.
    9. Compute the rectangle's sum as get(x2, y2) - get(x1-1, y2) - get(x2, y1-1) + get(x1-1, y1-1), all on partialSums.
    10. Update result when the sum is larger, and return it after all the loops.

    The solution in Go

    type Solution struct {}

func (this Solution) get(grid [][]int, i, j int) int {
    if i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0]) {
        return grid[i][j]
    }
    return 0
}

func (this Solution) maxSum(grid [][]int) int {
    result := grid[0][0]
    partialSums := make([][]int, len(grid))
    for i := range partialSums {
        partialSums[i] = make([]int, len(grid[0]))
    }

    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); 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 x1 := 0; x1 < len(grid); x1++ {
        for y1 := 0; y1 < len(grid[0]); y1++ {
            for x2 := x1; x2 < len(grid); x2++ {
                for y2 := y1; y2 < len(grid[0]); y2++ {
                    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)
                    if sum > result {
                        result = sum
                    }
                }
            }
        }
    }
    return result
}

    Go details:

    • A slice of slices. A [][]int is a slice whose elements are slices, so rows may in principle differ in length. The code assumes a rectangular grid and uses len(grid[0]) as the width.
    • for i := range partialSums with one variable ranges over the indices, which is exactly what is needed to make each row.
    • Line breaks and operators. Go inserts a semicolon at the end of a line that ends with an identifier, a literal or a closing bracket. That is why the broken lines in the code end with + or -: a line ending in an operator continues onto the next one. Starting the next line with the operator would be a syntax error.
    • Passing a slice shares data. get receives the slice header, not a copy of the numbers, so passing partialSums is cheap.
    • No overflow concerns. int is 64 bits, so ordinary grid values and their sums will not overflow.

    Worked check

    For the example grid, the prefix table is [[1 -8 -18 -17] [0 1 1 3] [0 10 19 12] [-1 8 16 8]]. For the corners (1, 1) to (2, 2), the terms are get(2,2) = 19, get(0,2) = -18, get(2,0) = 0 and get(0,0) = 1, so the sum is 19 - (-18) - 0 + 1 = 38.

    Complexity

    Time: O(m² * n²). Building the table takes O(m * n). The four nested loops visit every pair of corners, and each rectangle costs a constant number of lookups. For a 100 by 100 grid that is roughly 25 million rectangles, which is fine, but it grows quickly. The next lesson on this problem fixes two row boundaries and solves the column part as a maximum-subarray problem, which removes one factor of n.

    Space: O(m * n). The table has the same size as the grid.

    Edge cases and common mistakes

    • All negative grid. For [[-3, -1], [-2, -5]] the answer is -1, the best single cell. Starting result at 0 would give a wrong 0.
    • Subtracting the corner. Forgetting + get(x1-1, y1-1) subtracts the top-left overlap twice.
    • Row and column mix-ups. Index the grid as grid[row][col]. Passing (y, x) to get reads the wrong cell.
    • Unmade rows. Writing to partialSums[i][j] before the row is made panics, because the row is nil.
    • Loop bounds. x2 must start at x1 and y2 at y1, not at 0.

    Testing

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