You are given an m x n integer matrix grid.
We define an hourglass as a part of the matrix with the following form:
Return the maximum sum of the elements of an hourglass.
Note that an hourglass cannot be rotated and must be entirely contained within the matrix.
Example 1:
Input: grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]] Output: 30 Explanation: 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 Explanation: There is only one hourglass in the matrix, with the sum: 1 + 2 + 3 + 5 + 7 + 8 + 9 = 35.
Constraints:
m == grid.lengthn == grid[i].length3 <= m, n <= 1500 <= grid[i][j] <= 106The key idea in #2428 Maximum Sum of an Hourglass is to evaluate all possible hourglass patterns inside a 2D grid. An hourglass consists of 3 cells in the top row, 1 cell in the middle, and 3 cells in the bottom row. Since an hourglass requires three rows and three columns, valid centers can only appear within a limited range of the matrix.
A straightforward approach is to iterate through each possible top-left position of a 3×3 region and compute the hourglass sum directly. For each candidate position, add the three top elements, the center element, and the three bottom elements, then track the maximum value encountered.
This solution works efficiently because every cell is visited a constant number of times, leading to linear traversal of the grid. While prefix sums can help precompute row or region sums, the direct calculation approach is already optimal for this pattern.
The overall complexity depends on scanning the matrix once, making it practical even for larger grids.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Direct Hourglass Traversal | O(m × n) | O(1) |
| Prefix Sum Assisted Calculation | O(m × n) | O(m × n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Each 3x3 submatrix has exactly one hourglass.
Find the sum of each hourglass in the matrix and return the largest of these values.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, prefix sums can be used to precompute row or submatrix sums to speed up repeated calculations. However, because an hourglass contains only seven elements, directly summing them is already efficient and often simpler to implement.
Yes, matrix traversal problems like this frequently appear in coding interviews. They test your ability to identify patterns in grids, handle boundaries correctly, and compute results efficiently using simple iterations.
A 2D array or matrix is sufficient for this problem. Since the task involves scanning fixed patterns inside the grid, no additional complex data structures are required beyond simple iteration variables.
The optimal approach is to iterate through every valid 3×3 region of the matrix and compute the hourglass sum directly. For each position, add the top three cells, the middle cell, and the bottom three cells. Track the maximum sum encountered during the traversal.