Problem overview
The method maxSum receives a grid of integers, grid, with n rows and m columns. A subsquare is a block of cells with the same number of rows and columns. The method returns the largest sum of any subsquare. The grid may hold negative numbers, and a single cell counts as a 1x1 square.
In the example, the grid has four rows and four columns. The 2x2 block in rows 1 and 2, columns 1 and 2, holds 10, 10, 9, 9, which add up to 38. No square has a larger sum, so the answer is 38. For comparison, the best single cell is 10, and the 2x2 block just to its right (rows 1 and 2, columns 2 and 3) sums to only 11. The 3x3 block in rows 1 to 3 and columns 0 to 2 also sums to 38, so a larger square is not automatically better or worse: the sizes have to be compared by their sums.
Approach: try every square, add up its cells
A square is fixed by its top-left corner and its bottom-right corner, with the extra condition that its height equals its width. The brute-force idea is to loop over both corners, skip the pairs that don't form a square, add up the cells of each square that remains, and keep the largest sum.
It is slow, but it is easy to get right, and it shows what a faster solution has to avoid: adding the same cells again and again. Later lessons on partial sums speed up the inner sum.
Step by step
- A helper,
rectSum, adds up the cells of a rectangle given by its corners(x1, y1)and(x2, y2). Two nested loops visit every row fromx1tox2and every column fromy1toy2, both ends included. - In
maxSum, read the grid's size:nrows andmcolumns, taken fromgrid.lengthandgrid[0].length. - Start
resultatgrid[0][0], not at 0. A real square's sum is always available, and the answer can be negative when every cell is. - Loop over the top-left corner with
x1andy1. - Loop over the bottom-right corner with
x2fromx1andy2fromy1, so the second corner is never above or left of the first. - Keep only squares: the number of rows,
x2 - x1, must equal the number of columns,y2 - y1. - Update
resultwith the larger of itself andrectSumfor that square. - Return
result.
The solution in TypeScript
class Solution {
rectSum(grid: number[][], x1: number, y1: number, x2: number, y2: number): number {
let sum = 0
for (let x = x1; x <= x2; ++x) {
for (let y = y1; y <= y2; ++y) {
sum += grid[x][y]
}
}
return sum
}
maxSum(grid: number[][]): number {
let n = grid.length
let m = grid[0].length
let result = grid[0][0]
for (let x1 = 0; x1 < n; ++x1) {
for (let y1 = 0; y1 < m; ++y1) {
for (let x2 = x1; x2 < n; ++x2) {
for (let y2 = y1; y2 < m; ++y2) {
if (x2 - x1 === y2 - y1) {
result = Math.max(result, this.rectSum(grid, x1, y1, x2, y2))
}
}
}
}
}
return result
}
}
The TypeScript details worth knowing:
- The type
number[][]is an array of arrays of numbers. A cell is read withgrid[x][y]: first the row, then the column. The type is erased when the code compiles to JavaScript, so nothing checks at run time that the rows have equal lengths. - Semicolons are optional. This code leaves them out, and JavaScript's automatic semicolon insertion fills them in at the line ends. Either style works; keep one throughout a file.
===compares without conversion. It is the usual equality test in TypeScript, and both sides here are numbers.- Calling the helper.
rectSumis a method of the class, so it is called asthis.rectSum(...).
Complexity
Take a square grid with n rows and n columns.
Time: O(n⁵). The four loops produce about n⁴ combinations of corners, and the equality test discards all but about n³ of them. Each square of side s costs s² additions in rectSum, and the squares are up to n wide, so the additions add up to a total on the order of n⁵.
Space: O(1). The code uses a few numbers and doesn't copy the grid.
The cost explains why this is a first draft: a grid with 100 rows and columns already needs billions of additions. Reading each square's sum in constant time, from precomputed partial sums, is what brings it down.
Edge cases and common mistakes
- All cells negative. For
[[-5, -2], [-3, -4]]the answer is-2, a 1x1 square. Startingresultat 0 would return 0. - One row. For
[[5, -9, 4]]the only squares are single cells, so the answer is5. A rectangle such as[5, -9, 4]is not a square, and the equality test excludes it. - Inclusive ends. A 1x1 square has
x1 === x2andy1 === y2, so both loops inrectSummust use<=. With<they would add nothing for it. - Counting rectangles. Dropping the equality test turns the problem into the maximum sum over all submatrices, which is a different answer. In the example it would be larger than 38.
- Row and column order. In
grid[x][y],xpicks the row. Swapping them reads outside the grid on a non-square grid, and a read beyond a row givesundefinedand turns the sum intoNaN.
Testing
- The example grid gives
38. [[-5, -2], [-3, -4]]gives-2.[[5, -9, 4]]gives5.[[-3, -7, -1]]gives-1.