LESSON 246 OF 414 · PARTIAL SUMS #2

Maximum Sum Subsquare in Scala: Brute Force over All Squares

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

SCALA · PARTIAL SUMS #2

Max Sum Square in Scala, explained

Problem overview

The method maxSum receives a grid of integers, an Array[Array[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, so 1x1, 2x2, 3x3 and so on.

In the example, the grid has four rows and four columns:

[ 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]] in the middle, with sum 38. Its cells are the ones at rows 1 and 2, columns 1 and 2.

Approach: try every square

A square is determined by its top-left corner (x1, y1) and its bottom-right corner (x2, y2), and it is a square exactly when x2 - x1 == y2 - y1. The simplest solution tries every pair of corners, skips the pairs that aren't squares, adds up the cells of each square with a helper, and keeps the best sum.

This is a brute-force approach. It is not the fastest one, because the helper adds up all the cells of each square from scratch. Precomputed prefix sums would make that part constant-time, but the brute force is the clearest way to see the structure of the problem, and it passes the lesson's tests.

Step by step

Read the dimensions. n is grid.length, the number of rows. m is grid(0).length, the number of columns of the first row, which is the same for every row.
Start result at grid(0)(0). Every grid contains at least that 1x1 square, so it is a valid starting answer. Starting at 0 would be wrong when every cell is negative.
Choose the top-left corner with two loops: x1 over the rows and y1 over the columns.
Choose the bottom-right corner with two more loops. x2 starts at x1 and y2 starts at y1, so the corner is never above or to the left of the first one.
Keep only squares. Test x2 - x1 == y2 - y1.
Sum the square with rectSum(grid, x1, y1, x2, y2) and compare it with result using math.max.
Write rectSum. It adds up every cell with x from x1 to x2 and y from y1 to y2. Both ends are included, so it uses to, not until.
Return result as the last expression.

The solution in Scala

class Solution {
    def rectSum(grid: Array[Array[Int]], x1: Int, y1: Int, x2: Int, y2: Int): Int = {
        var sum = 0
        for (x <- x1 to x2) {
            for (y <- y1 to y2) {
                sum += grid(x)(y)
            }
        }
        sum
    }

    def maxSum(grid: Array[Array[Int]]): Int = {
        val n = grid.length
        val m = grid(0).length
        var result = grid(0)(0)
        for (x1 <- 0 until n) {
            for (y1 <- 0 until m) {
                for (x2 <- x1 until n) {
                    for (y2 <- y1 until m) {
                        if (x2 - x1 == y2 - y1) {
                            result = math.max(result, rectSum(grid, x1, y1, x2, y2))
                        }
                    }
                }
            }
        }
        result
    }
}

The Scala details worth a closer look:

Array[Array[Int]] is an array of rows. The cell in row x and column y is grid(x)(y): first the row array, then the element in it. Scala uses parentheses for indexing, not square brackets.
to versus until. x1 to x2 includes x2, which rectSum needs because the bottom-right corner is part of the square. 0 until n excludes n, which suits the loops over valid indices. The inner loops x2 <- x1 until n and y2 <- y1 until m also stop before n and m.
Nested for loops. Each for (a <- range) runs its body once per value in the range. Writing them as separate nested loops, as the lesson does, keeps each level clear.
var sum = 0 inside rectSum is local to the method and changes as cells are added. The method's last expression, sum, is its result.
Result of the last line. In maxSum, the final result has no return before it, which is the usual Scala style.

Complexity

Let the grid be n by m, and let s be the smaller of the two.

Time. The four nested loops look at O(n²m²) pairs of corners. Of those, only about n * m * s pairs form squares, and each square of side k costs k² additions in rectSum. For an n by n grid the total is O(n⁵). That is fine for small grids and slow for large ones.

Space: O(1). Only a handful of integers are kept, and the grid is never copied.

Edge cases and common mistakes

A single cell. maxSum(Array(Array(7))) returns 7, because the 1x1 square is the only square.
All negative cells. For [[-5, -2], [-3, -4]] the answer is -2, the single cell closest to zero. The 2x2 sum is -14. That is why result starts at the first cell and not at 0.
A rectangular grid. For [[1, 2, 3], [4, 5, 6]] there is no 3x3 square, because the grid has only two rows. The best square is the 2x2 block [[2, 3], [5, 6]], with sum 16. Starting x2 at x1 and stopping at n keeps every candidate inside the grid.
Counting rectangles. Without the x2 - x1 == y2 - y1 test the method would report the best rectangle, a different problem.
Using until in rectSum. The last row and column of the square would be missing from the sum.
Taking a larger square for being larger. A bigger square can have a smaller sum when it includes negative cells. In a 3x3 grid with -1 everywhere except a 5 in the center, the single center cell, 5, beats the whole grid.

Testing

The example grid above gives 38.
[[7]] gives 7.
[[-5, -2], [-3, -4]] gives -2.
[[1, 2, 3], [4, 5, 6]] gives 16.
[[-1, -1, -1], [-1, 5, -1], [-1, -1, -1]] gives 5.

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

Start learning free