LeetCode 2428 - Maximum Sum of an Hourglass

The problem provides an m x n integer matrix grid and asks for the maximum sum of an hourglass shape within the matrix. An hourglass is defined as a 3x3 structure with the top and bottom rows fully included, and only the center element from the middle row.

leetcodemediumarraymatrixprefix-sum

LeetCode Problem 2428

Difficulty: 🟡 Medium
Topics: Array, Matrix, Prefix Sum

Solution

Problem Understanding

The problem provides an m x n integer matrix grid and asks for the maximum sum of an hourglass shape within the matrix. An hourglass is defined as a 3x3 structure with the top and bottom rows fully included, and only the center element from the middle row. Specifically, if i and j denote the top-left coordinates of an hourglass, the hourglass sum is:

grid[i][j] + grid[i][j+1] + grid[i][j+2]
          + grid[i+1][j+1] +
grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2]

The matrix dimensions are guaranteed to be at least 3x3, so there is always at least one valid hourglass. The constraints 3 <= m, n <= 150 and 0 <= grid[i][j] <= 10^6 indicate that a straightforward brute-force solution iterating over all possible hourglass positions is feasible, but we should also consider optimizations using precomputed sums if needed.

Edge cases to consider include the smallest possible matrix 3x3 (exactly one hourglass) and matrices where all values are the same (testing whether the code correctly identifies the maximum even when sums are identical).

Approaches

The brute-force approach iterates over every possible top-left position (i, j) of a 3x3 hourglass. For each position, it explicitly sums the 7 relevant elements. This approach guarantees correctness because it literally checks every valid hourglass, but it may perform redundant calculations across overlapping hourglasses. The time complexity is O((m-2)*(n-2)*7) which simplifies to O(m*n) and is acceptable for the given constraints. Space complexity is O(1) since no extra data structures are required.

The optimal approach uses the same brute-force scan but leverages the fact that summing individual elements in a fixed 3x3 pattern is simple and does not require advanced techniques like prefix sums, given the small constant factor. For larger hourglass-like problems or variable sizes, one might use a prefix sum to compute row or submatrix sums more efficiently, but here the simplicity and fixed pattern make a direct calculation optimal.

Approach Time Complexity Space Complexity Notes
Brute Force O(m*n) O(1) Iterate all top-left positions of hourglass and sum 7 elements each
Optimal O(m*n) O(1) Same as brute force; the constant factor is small and no extra storage is needed

Algorithm Walkthrough

  1. Initialize a variable max_sum to 0 or negative infinity to track the largest hourglass sum found. Using negative infinity ensures correctness if grid could contain zeroes only.
  2. Iterate over all valid top-left positions (i, j) of the hourglass. Valid positions satisfy 0 <= i <= m-3 and 0 <= j <= n-3.
  3. For each (i, j), compute the hourglass sum explicitly using the formula above.
  4. Compare the computed sum to max_sum, and update max_sum if the new sum is larger.
  5. After finishing the iteration, return max_sum as the final result.

Why it works: The algorithm checks every possible hourglass in the matrix exactly once. Since the sum for each hourglass is computed correctly and compared against the running maximum, the final value of max_sum is guaranteed to be the largest possible hourglass sum in the matrix.

Python Solution

from typing import List

class Solution:
    def maxSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        max_sum = 0
        
        for i in range(m - 2):
            for j in range(n - 2):
                current_sum = (
                    grid[i][j] + grid[i][j+1] + grid[i][j+2] +
                    grid[i+1][j+1] +
                    grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2]
                )
                if i == 0 and j == 0:
                    max_sum = current_sum
                else:
                    max_sum = max(max_sum, current_sum)
                    
        return max_sum

Explanation: We first determine the dimensions m and n. The outer loops iterate through all positions where a 3x3 hourglass fits. The sum for the hourglass is computed explicitly using the indices, including the top row, middle center, and bottom row. The maximum sum is updated at each step. We initialize max_sum on the first hourglass to ensure correctness even if all values are zero.

Go Solution

func maxSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    maxSum := 0
    first := true

    for i := 0; i <= m-3; i++ {
        for j := 0; j <= n-3; j++ {
            currentSum := grid[i][j] + grid[i][j+1] + grid[i][j+2] +
                          grid[i+1][j+1] +
                          grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2]
            if first {
                maxSum = currentSum
                first = false
            } else if currentSum > maxSum {
                maxSum = currentSum
            }
        }
    }
    return maxSum
}

Go-specific notes: We handle initialization carefully using a boolean first because Go does not have negative infinity for integers. Other than syntax differences, the logic mirrors the Python version. There is no risk of nil slices because the problem constraints guarantee a valid matrix.

Worked Examples

Example 1:

grid = [[6,2,1,3],
        [4,2,1,5],
        [9,2,8,7],
        [4,1,2,9]]

Iteration steps:

i j Hourglass Elements Sum max_sum
0 0 6,2,1,2,9,2,8 30 30
0 1 2,1,3,1,2,8,7 24 30
1 0 4,2,1,2,4,1,2 16 30
1 1 2,1,5,8,1,2,9 28 30

Final result: 30

Example 2:

grid = [[1,2,3],
        [4,5,6],
        [7,8,9]]

Only one hourglass exists:

1 + 2 + 3 + 5 + 7 + 8 + 9 = 35

Final result: 35

Complexity Analysis

Measure Complexity Explanation
Time O(m*n) We iterate over all valid top-left positions of a 3x3 hourglass. Each sum calculation takes O(1) since only 7 elements are summed.
Space O(1) We only store the running maximum and temporary sum; no extra data structures proportional to input size are used.

The algorithm is efficient given the constraints, since m*n is at most 150*150 = 22500 iterations, each very lightweight.

Test Cases

# Provided examples
assert Solution().maxSum([[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]) == 30  # Example 1
assert Solution().maxSum([[1,2,3],[4,5,6],[7,8,9]]) == 35  # Example 2

# Minimum size matrix
assert Solution().maxSum([[1,1,1],[1,1,1],[1,1,1]]) == 7  # single hourglass sum

# Large uniform matrix
assert Solution().maxSum([[10**6]*150 for _ in range(150)]) == 7*10**6  # all max values

# Mixed values
assert Solution().maxSum([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]) == 73  # non-trivial max

# Edge with zeros
assert Solution().maxSum([[0,0,0],[0,0,0],[0,0,0]]) == 0
Test Why
Example 1 Verifies correct calculation with multiple hourglasses
Example 2 Handles smallest 3x3 matrix
Minimum size Confirms single hourglass is handled
Large uniform Tests upper bound and large numbers
Mixed values Confirms correct identification of maximum sum
Edge with zeros Checks zero handling

Edge Cases

  1. Minimum Matrix Size (3x3): There