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] <= 106Problem Overview: Given an m x n grid, find the maximum sum of an hourglass shape. An hourglass uses 7 cells: three from the top row, one from the middle, and three from the bottom row. You must evaluate every valid hourglass in the matrix and return the largest sum.
Approach 1: Brute Force Matrix Traversal (Time: O(m*n), Space: O(1))
The direct approach scans every possible 3x3 region that can form an hourglass. For each top-left coordinate (i, j), compute the sum of the seven required cells: grid[i][j..j+2], grid[i+1][j+1], and grid[i+2][j..j+2]. Track the maximum while iterating through the grid. Each hourglass calculation touches only 7 elements, so the overall complexity becomes O(m*n) with constant O(1) extra space. This approach is straightforward and works well because the hourglass size is fixed.
Approach 2: Sliding Window Optimization (Time: O(m*n), Space: O(1))
You can reduce repeated calculations by sliding a window across columns. Instead of recomputing all three cells of the top and bottom rows for every position, maintain partial sums of the 3‑element windows while moving from left to right. Subtract the element leaving the window and add the new element entering it. Combine these row sums with the center element grid[i+1][j+1] to compute the hourglass total. This technique keeps the complexity at O(m*n) but reduces constant work per position. It relies on ideas similar to prefix sum or k-length window reuse.
Both approaches rely heavily on structured traversal of a matrix and careful indexing inside a 2D array. Since the hourglass shape is fixed, the real challenge is writing clean iteration bounds and avoiding out-of-range indices.
Recommended for interviews: Start with the brute force traversal since it clearly shows you understand the hourglass structure and matrix boundaries. After that, mention the sliding window optimization to demonstrate awareness of avoiding redundant computation. Interviewers typically expect the O(m*n) traversal, but discussing the window reuse shows stronger algorithmic thinking.
In this basic approach, iterate through each possible position in the grid that can be the top-left corner of an hourglass. For each position, calculate the sum of the corresponding hourglass and keep track of the maximum sum encountered. Because an hourglass cannot rotate or extend beyond matrix boundaries, only consider positions where a full hourglass can fit.
This C function, maxHourglassSum, iterates through the grid's valid hourglass start positions. For each valid start, it calculates the sum by accessing fixed indices of the hourglass shape, then it updates the maximum found sum.
Time Complexity: O(m * n), where m and n are grid dimensions, limited by hourglass boundaries. Space Complexity: O(1), using constant extra space for variables only.
This optimized approach uses a sliding window technique, updating the hourglass sum by only changing the elements that have been added or removed as the window slides over the matrix. The idea is to leverage previous calculations, cutting down redundant sum computations.
This C solution improves performance by adjusting the sum using established values as the hourglass shape shifts across the row, reducing repetitive computations.
Time Complexity: O(m * n), efficiently iterating over matrix in single full pass while updating hourglass sums. Space Complexity: O(1), as only essential variables are used.
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.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(m * n), where m and n are grid dimensions, limited by hourglass boundaries. Space Complexity: O(1), using constant extra space for variables only. |
| Optimized Sliding Window Approach | Time Complexity: O(m * n), efficiently iterating over matrix in single full pass while updating hourglass sums. Space Complexity: O(1), as only essential variables are used. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Matrix Traversal | O(m*n) | O(1) | Best for clarity and interviews when the hourglass size is fixed. |
| Sliding Window Optimization | O(m*n) | O(1) | When you want to reduce repeated row calculations while scanning large matrices. |
Maximum Sum of an Hourglass | leetcode Weekly 313 | Leetcode Medium • BinaryMagic • 3,397 views views
Watch 9 more video solutions →Practice Maximum Sum of an Hourglass with our built-in code editor and test cases.
Practice on FleetCode