#2428

Medium

LeetCode Problem Workspace

Maximum Sum of an Hourglass

Calculate the maximum sum of an hourglass in a 2D matrix using array traversal and submatrix evaluation techniques efficiently.

array matrix prefix sum

Problem Statement

You are given an m x n integer matrix called grid. An hourglass is defined as a 3x3 section of the matrix shaped with three elements on the top row, one in the middle, and three on the bottom row. Your task is to calculate the sum of elements in each hourglass and return the maximum sum found.

For example, in a 4x4 grid, multiple hourglasses can overlap, and each 3x3 submatrix contains exactly one hourglass. You must scan all valid positions and compute their sums efficiently to identify the maximum possible hourglass sum.

Examples

Example 1

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

Output: 30

The cells shown above represent the hourglass with the maximum sum: 6 + 2 + 1 + 2 + 9 + 2 + 8 = 30.

Example 2

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

Output: 35

There is only one hourglass in the matrix, with the sum: 1 + 2 + 3 + 5 + 7 + 8 + 9 = 35.

Constraints

m == grid.length
n == grid[i].length
3 <= m, n <= 150
0 <= grid[i][j] <= 106

Solution Approach

Brute Force Traversal

Iterate through all valid top-left positions of a 3x3 submatrix. For each position, calculate the hourglass sum by adding the top row, middle element, and bottom row. Track the maximum sum throughout traversal. This approach directly follows the array plus matrix pattern but may be slower for large grids.

Prefix Sum Optimization

Compute prefix sums for rows or the entire matrix to quickly calculate sums of hourglass components. This reduces redundant addition operations by leveraging precomputed sums. It minimizes repeated calculations when moving the 3x3 window across the matrix.

Sliding Window Technique

Apply a sliding 3x3 window across the matrix, updating the hourglass sum incrementally rather than recomputing from scratch. Add new elements entering the window and remove elements leaving to maintain efficiency. This aligns with the problem's pattern of overlapping submatrices.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * n) because each 3x3 hourglass is visited once. Space complexity can be O(1) for brute force or O(m * n) if using full prefix sum arrays. Optimization depends on chosen approach.

What Interviewers Usually Probe

Expect questions on how to iterate without index errors when handling the 3x3 hourglass shape.
Look for recognition of overlapping submatrices and opportunities to optimize with prefix sums.
Evaluate how candidates track maximum sums efficiently and avoid redundant calculations.

Common Pitfalls or Variants

Common pitfalls

Forgetting that hourglass centers are single elements in the middle row, causing incorrect sums.
Accessing indices outside matrix bounds when looping near edges.
Recomputing entire sums for overlapping hourglasses instead of using sliding updates or prefix sums.

Follow-up variants

Compute minimum sum of an hourglass instead of maximum sum.
Handle non-square matrices or variable hourglass sizes, e.g., 4x4 patterns.
Return coordinates of the hourglass with maximum sum along with the sum.

FAQ

What is an hourglass in the context of this matrix problem?

An hourglass is a 3x3 submatrix with three elements on the top row, one in the middle, and three on the bottom row.

Can I use prefix sums to optimize maximum hourglass sum calculation?

Yes, prefix sums allow rapid calculation of row or matrix sections, reducing repeated addition when scanning overlapping hourglasses.

What happens if the matrix is smaller than 3x3?

There will be no valid hourglass, so the problem constraints require m and n to be at least 3.

Does GhostInterview suggest sliding window optimizations?

Yes, it identifies opportunities to update hourglass sums incrementally as the window moves across the matrix.

How does the array plus matrix pattern apply here?

Each hourglass is a fixed submatrix, and iterating through all top-left positions demonstrates the array plus matrix pattern with overlapping submatrices.

terminal

Solution

Solution 1: Enumeration

We observe from the problem statement that each hourglass is a $3 \times 3$ matrix with the first and last elements of the middle row removed. Therefore, we can start from the top left corner, enumerate the middle coordinate $(i, j)$ of each hourglass, then calculate the sum of the elements in the hourglass, and take the maximum value.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                s = -grid[i][j - 1] - grid[i][j + 1]
                s += sum(
                    grid[x][y] for x in range(i - 1, i + 2) for y in range(j - 1, j + 2)
                )
                ans = max(ans, s)
        return ans

Continue Practicing

#2536 increment submatrices by one #2245 maximum trailing zeros in a cornered path #2132 stamping the grid