LESSON 223 OF 348 · PARTIAL SUMS #2

Max Sum Square in Kotlin: Brute Force Over All Subsquares

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

Given a n x m grid filled with integers, find the subsquare with maximum sum among all submatrices.

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

KOTLIN · PARTIAL SUMS #2

Max Sum Square in Kotlin, explained

Problem overview

The function maxSum receives a grid of integers as an Array<IntArray> with n rows and m columns. It returns the largest sum of any subsquare: a block of neighbouring cells that has the same number of rows and columns. The numbers may be negative.

In the example grid, the best subsquare is the 2x2 block [[10, 10], [9, 9]] in the middle, with sum 38. Single cells are 1x1 subsquares too, so the answer is never smaller than the largest single value.

Approach: enumerate every rectangle, keep the squares

A rectangle in the grid is fixed by two corners: the top-left (x1, y1) and the bottom-right (x2, y2). Four nested loops generate every such pair with x2 >= x1 and y2 >= y1. A rectangle is a square when its height x2 - x1 + 1 equals its width y2 - y1 + 1, which simplifies to x2 - x1 == y2 - y1. For each square, a helper adds up its cells, and the answer keeps the largest sum.

This is the simplest correct method, and it is slow: it visits every rectangle and then sums its cells one by one. Prefix sums on a grid could answer each rectangle's sum in constant time, but this lesson keeps the idea plain.

Here is how the example's best block is found. When x1 = 1, y1 = 1, x2 = 2 and y2 = 2, both differences are 1, so the test passes. rectSum adds 10 + 10 + 9 + 9 and returns 38. A neighbouring rectangle such as rows 1 to 2 and columns 1 to 3 has a height of 2 and a width of 3, so the test rejects it and its sum is never computed.

Step by step

Write rectSum. It takes the grid and the corners x1, y1, x2, y2, loops over x from x1 to x2 and y from y1 to y2, both inclusive, and adds each grid[x][y] to a running sum.
Read the dimensions in maxSum: n is the number of rows and m the number of columns, taken from the first row.
Start result at grid[0][0], a real subsquare's sum. Starting at 0 would be wrong for a grid of negative numbers, where the answer is negative.
Choose the top-left corner with x1 over the rows and y1 over the columns.
Choose the bottom-right corner with x2 from x1 and y2 from y1, so it is never above or left of the top-left corner.
Keep only squares with the test x2 - x1 == y2 - y1.
Update result with the larger of the old value and rectSum of the current square, then return it.

The solution in Kotlin

class Solution {
    fun rectSum(grid: Array<IntArray>, 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
    }

    fun maxSum(grid: Array<IntArray>): Int {
        val n = grid.size
        val m = grid[0].size
        var result = grid[0][0]
        for (x1 in 0 until n) {
            for (y1 in 0 until m) {
                for (x2 in x1 until n) {
                    for (y2 in y1 until m) {
                        if (x2 - x1 == y2 - y1) {
                            result = maxOf(result, rectSum(grid, x1, y1, x2, y2))
                        }
                    }
                }
            }
        }
        return result
    }
}

Kotlin details worth knowing:

Array<IntArray> is an array of rows. Each element is an IntArray, and grid[x][y] reads row x, column y. grid.size is the number of rows, and grid[0].size is the length of the first row.
.. is inclusive, until is not. x1..x2 includes x2, which is what a corner coordinate needs. 0 until n stops at n - 1, the last valid index.
sum and result are var. They change as the loops run. The grid and the corner parameters never change, and Kotlin parameters can't be reassigned anyway.
Int wraps silently on overflow. A huge grid of huge values could overflow; Long would be needed then.

Complexity

Let the grid have n rows and m columns.

Time. The four loops visit up to O(n² · m²) pairs of corners, but only squares are summed, and a square of side s costs s² additions. In the worst case, a square grid of side n, that comes to O(n⁵) in total, which is slow beyond small grids. The loops still run through all the non-square rectangles to reject them, which is wasted work.

Space: O(1). Only a few integers are kept, and the grid is not copied or changed.

Edge cases and common mistakes

All negative values. For [[-1, -2], [-3, -4]] the answer is -1, the best single cell. The 2x2 block sums to -10.
A one-cell grid. The loops produce one square, the cell itself.
Non-square grids. A 2x3 grid has squares of side 1 and 2 only. Side 3 doesn't fit, and the corner loops never produce it.
Using until in rectSum. That drops the last row and column of the square, so every sum is too small.
Testing x2 == y2. That only accepts squares along the main diagonal. Compare the differences x2 - x1 and y2 - y1.
Mixing up rows and columns. In grid[x][y], x picks the row and y the column. Using grid[0].size for the row count, or grid.size for the column count, breaks every grid that isn't square.
Summing inside the wrong loop. Calling rectSum before the square test sums every rectangle, including the ones that must be ignored. That gives wrong answers for grids where a non-square rectangle has a larger sum.
Starting result at 0. It wrongly beats every negative sum.

Testing

The statement's 4x4 grid gives 38.
[[-1, -2], [-3, -4]] gives -1.
[[1, 2, 3], [4, 5, 6]] gives 16, from the 2x2 block [[2, 3], [5, 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