Skip to main content
Talentd

Maximum Sum of an Hourglass - Solution & Explanation

MediumArrayMatrixPrefix Sum16 min readAsked at: Nutanix
Practice this problem

Problem Statement

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.length
  • n == grid[i].length
  • 3 <= m, n <= 150
  • 0 <= grid[i][j] <= 106

Approach Overview

Problem 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 1: Brute Force Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Optimized Sliding Window Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Matrix TraversalO(m*n)O(1)Best for clarity and interviews when the hourglass size is fixed.
Sliding Window OptimizationO(m*n)O(1)When you want to reduce repeated row calculations while scanning large matrices.

Video Solution

Maximum Sum of an Hourglass | leetcode Weekly 313 | Leetcode Medium • BinaryMagic • 3,412 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Sum of an Hourglass easy or hard?
Maximum Sum of an Hourglass is generally considered a medium-level problem. The main difficulty comes from correctly handling matrix boundaries and implementing the hourglass pattern without indexing mistakes. Once the pattern is clear, the implementation is straightforward.
Maximum Sum of an Hourglass Python/Java solution
In Python or Java, iterate through indices from 0 to m-3 and 0 to n-3, compute the seven elements forming the hourglass, and update the maximum sum. The logic is identical across languages and runs in O(m*n) time with constant space.
How to solve Maximum Sum of an Hourglass in O(n)?
Treat n as the total number of cells in the matrix. Iterate through every possible top-left position of a 3x3 hourglass and compute its sum. Because each hourglass calculation takes constant time, the entire traversal runs in linear time relative to the number of grid cells, O(m*n).
What is the best approach for Maximum Sum of an Hourglass?
The best approach is scanning every valid 3x3 region of the grid and computing the hourglass sum. Since the hourglass size is fixed, this traversal runs in O(m*n) time and O(1) extra space. Some implementations optimize repeated row calculations using a sliding window, but the overall complexity remains the same.
Is Maximum Sum of an Hourglass asked at Google/Amazon/Meta?
Matrix traversal and pattern-sum problems similar to Maximum Sum of an Hourglass appear in interviews at companies like Amazon and Google. They test your ability to handle 2D array indexing, boundary conditions, and efficient iteration through grid structures.
What data structure is used in Maximum Sum of an Hourglass?
The core data structure is a 2D array (matrix). The algorithm iterates through the matrix and computes sums of specific positions forming the hourglass pattern. Some optimized implementations reuse row sums with sliding window or prefix-sum style techniques.
What is the time complexity of Maximum Sum of an Hourglass?
The time complexity is O(m*n), where m and n are the grid dimensions. Each valid hourglass is evaluated once, and each evaluation touches only 7 cells. The space complexity stays O(1) because only a few variables are used to track the current and maximum sums.

Ready to solve this problem?

Practice Maximum Sum of an Hourglass with our built-in code editor and test cases.

Practice on FleetCode
Previous

Matrix Block Sum