LESSON 247 OF 415 · PARTIAL SUMS #2

Maximum Sum Subsquare in Swift: Brute Force over Corners

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

Given a n x m grid filled with integers, find the maximum sum of a subsquare (return that sum).

Example:

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

Note: A subsquare is a submatrix having the same number of columns and rows

SOLVE IT YOURSELF

Ctrl + Enter to check

SWIFT · PARTIAL SUMS #2

Max Sum Square in Swift, explained

Problem overview

The method maxSum receives a grid of integers, an [[Int]] with n rows and m columns. It must find the subsquare with the largest sum and return that sum. A subsquare is a block of neighbouring cells with the same number of rows and columns. Cells can be negative, so a bigger square isn't always better, and a single cell counts as a 1x1 subsquare.

In the example the grid is:

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

The best subsquare is the 2x2 block [[10, 10], [9, 9]], whose sum is 38.

Approach: try every square, add up its cells

A subsquare is fixed by its top-left corner (x1, y1) and its bottom-right corner (x2, y2). It is a square exactly when its height equals its width, that is, x2 - x1 == y2 - y1.

The simplest solution enumerates all pairs of corners with four nested loops. For each pair that forms a square, it adds up the cells with a helper and keeps the largest sum. It isn't fast, but it is easy to get right, and it is a baseline for faster versions that use prefix sums to read any square's sum in constant time.

Step by step

Write a helper, rectSum, that takes the grid and the two corners (x1, y1, x2, y2) and returns the sum of the cells they enclose, with both corners included. It starts at sum = 0, loops x from x1 to x2 and y from y1 to y2, and adds grid[x][y].
Read the size of the grid. n = grid.count is the number of rows, and m = grid[0].count is the number of columns, taken from the first row.
Start result at grid[0][0], not at 0. The value must be a real subsquare's sum, because every cell may be negative and the best square would then be negative too.
Choose the top-left corner with loops over x1 in 0..<n and y1 in 0..<m.
Choose the bottom-right corner with loops over x2 from x1 and y2 from y1. Starting at the top-left corner keeps the bottom-right at or below and to the right of it.
Keep only squares. If x2 - x1 == y2 - y1, the block is a square.
Update result with the larger of itself and the square's sum from rectSum.
Return result when the loops finish.

The solution in Swift

class Solution {
    func rectSum(_ grid: [[Int]], _ x1: Int, _ y1: Int, _ x2: Int, _ y2: Int) -> Int {
        var sum = 0
        for x in x1...x2 {
            for y in y1...y2 {
                sum += grid[x][y]
            }
        }
        return sum
    }

    func maxSum(_ grid: [[Int]]) -> Int {
        let n = grid.count
        let m = grid[0].count
        var result = grid[0][0]
        for x1 in 0..<n {
            for y1 in 0..<m {
                for x2 in x1..<n {
                    for y2 in y1..<m {
                        if x2 - x1 == y2 - y1 {
                            result = max(result, rectSum(grid, x1, y1, x2, y2))
                        }
                    }
                }
            }
        }
        return result
    }
}

Swift details worth knowing:

Closed and half-open ranges. x1...x2 includes x2, which is what rectSum needs, because the corner is part of the block. 0..<n and x1..<n exclude n, which suits row and column indices. A closed range a...b needs a <= b, and the loops guarantee it, since x2 starts at x1 and y2 at y1.
Nested arrays. A grid is an array of arrays, so a cell is read as grid[row][column], with two sets of brackets. The type [[Int]] doesn't force the rows to have equal lengths, so the code assumes a rectangular grid.
Passing the grid is cheap. Arrays are value types, but Swift copies the storage only when someone changes it. rectSum only reads, so no copy is made on each call.
max. The global max(a, b) returns the larger of two values.
Methods calling methods. rectSum(grid, ...) is called without self., and the underscores in its declaration (_ grid, _ x1, ...) mean the call carries no argument labels.

Complexity

Let n and m be the grid's dimensions.

Time: O(n² · m²). The four loops visit up to about n · m · n · m / 4 pairs of corners. Most pairs are rejected by the square test in constant time. The ones that pass cost s² each for a square of side s, and over all top-left corners the squares cost O(n · m · min(n, m)³), which doesn't exceed O(n² · m²). Summing a square directly is the part that prefix sums can replace.

Space: O(1). Besides the input, only a few integers are stored.

Edge cases and common mistakes

All cells negative. For [[-1, -2], [-3, -4]] the answer is -1, a single cell. A starting value of 0 would return 0, which no subsquare has.
One row or one column. Only 1x1 squares exist. For [[-4, -2, -7]] the answer is -2.
A single cell. [[5]] returns 5.
Non-square grids. For a 2x3 grid [[1, 2, 3], [4, 5, 6]] the largest square has side 2, and the best one is [[2, 3], [5, 6]] with sum 16.
Bigger is not better. For [[-5, 4], [4, -5]] the whole 2x2 square sums to -2, but a single cell holds 4, so the answer is 4. The statement's example shows it too: the whole 4x4 grid sums to 12, far below the 38 of the block inside it.
Checking only the side lengths. The condition x2 - x1 == y2 - y1 compares differences. Comparing x2 == y2 instead would only accept squares on the diagonal.
Confusing rows and columns. x is the row, the first index, and y is the column, the second.

Testing

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

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

Start learning free