Watch 10 video solutions for Maximum Sum of an Hourglass, a medium level problem involving Array, Matrix, Prefix Sum. This walkthrough by BinaryMagic has 3,397 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |