Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum Sum of an Hourglass solution and explanation

MediumArrayMatrixPrefix Sum5 min read77.1% acceptanceUpdated 9 Apr 2026
Asked atNutanix
Practise Maximum Sum of an Hourglass
8:23
Maximum Sum of an Hourglass | leetcode Weekly 313 | Leetcode MediumBinaryMagic · 8:23 · 3K viewsWatch on YouTube
9 more videos on this problem
  1. Maximum Sum of an Hourglass | leetcode Weekly 313 | Leetcode MediumBinaryMagic · 8:23 · 3K views
  2. Leetcode 2428 Maximum Sum of an Hourglass | HindiThinkCode · 9:49 · 858 views
  3. Leetcode 2428: Maximum Sum of an HourglassAlgorithms Casts · 8:16 · 767 views
  4. 2428. Maximum Sum of an Hourglass (Leetcode Medium)Programming Live with Larry · 4:10 · 491 views
  5. Leetcode 2428. Maximum Sum of an Hourglass [Solution]Elite Code · 10:01 · 406 views
  6. Maximum Sum of an Hourglass || LeetCode Weekly Contest 313 || C++Priyanshi Porwal · 4:08 · 296 views
  7. 2428. Maximum Sum of an Hourglass || Leetcode Contest Medium || Array || CPPCoding Techniques with Komal | Newton School · 11:46 · 261 views
  8. Leetcode Weekly contest 313 - Medium - Maximum Sum of an HourglassPrakhar Agrawal · 8:06 · 244 views
  9. Leetcode Problem 2428 - Max Sum of HourglassNevan Samadhana · 11:48 · 205 views
  10. Leetcode with 2D Prefix Sums (2428 Maximum Hourglass Sum) Part 2Benn Tan · 18:20 · 194 views

The problem

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.

def max_hourglass_sum(grid):
    max_sum = float('-inf')
    m = len(grid)
    n = len(grid[0])
    
    for i in range(m - 2):
        for j in range(n - 2):
            hourglass_sum = (grid[i][j] + grid[i][j+1] + grid[i][j+2] +
                            grid[i+1][j+1] +
                            grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2])
            max_sum = max(max_sum, hourglass_sum)

    return max_sum

grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]
print("Maximum Hourglass Sum:", max_hourglass_sum(grid))
public class Solution {
    public static int maxHourglassSum(int[][] grid) {
        int maxSum = Integer.MIN_VALUE;
        int m = grid.length, n = grid[0].length;
        
        for (int i = 0; i < m - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                int sum = grid[i][j] + grid[i][j+1] + grid[i][j+2]
                          + grid[i+1][j+1]
                          + grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2];
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[][] grid = {{6,2,1,3},{4,2,1,5},{9,2,8,7},{4,1,2,9}};
        System.out.println("Maximum Hourglass Sum: " + maxHourglassSum(grid));
    }
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxHourglassSum(const vector<vector<int>>& grid) {
    int maxSum = INT_MIN;
    int m = grid.size();
    int n = grid[0].size();
    
    for (int i = 0; i < m - 2; i++) {
        for (int j = 0; j < n - 2; j++) {
            int sum = grid[i][j] + grid[i][j+1] + grid[i][j+2]
                      + grid[i+1][j+1]
                      + grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2];
            maxSum = max(maxSum, sum);
        }
    }
    return maxSum;
}

int main() {
    vector<vector<int>> grid = {{6,2,1,3},{4,2,1,5},{9,2,8,7},{4,1,2,9}};
    cout << "Maximum Hourglass Sum: " << maxHourglassSum(grid);
    return 0;
}
function maxHourglassSum(grid) {
    let maxSum = -Infinity;
    let m = grid.length;
    let n = grid[0].length;

    for (let i = 0; i < m - 2; i++) {
        for (let j = 0; j < n - 2; j++) {
            let sum = grid[i][j] + grid[i][j+1] + grid[i][j+2] +
                      grid[i+1][j+1] +
                      grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2];
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

let grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]];
console.log("Maximum Hourglass Sum:", maxHourglassSum(grid));
#include <stdio.h>

int maxHourglassSum(int grid[][150], int m, int n) {
    int maxSum = 0;
    for (int i = 0; i < m - 2; i++) {
        for (int j = 0; j < n - 2; j++) {
            int hourglassSum = grid[i][j] + grid[i][j + 1] + grid[i][j + 2] +
                               grid[i + 1][j + 1] +
                               grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2];
            if (i == 0 && j == 0) maxSum = hourglassSum;
            if (hourglassSum > maxSum) maxSum = hourglassSum;
        }
    }
    return maxSum;
}

int main() {
    int grid[4][150] = {{6, 2, 1, 3}, {4, 2, 1, 5}, {9, 2, 8, 7}, {4, 1, 2, 9}};
    int maxSum = maxHourglassSum(grid, 4, 4);
    printf("Maximum Hourglass Sum: %d", maxSum);
    return 0;
}
using System;

class Solution {
    public static int MaxHourglassSum(int[,] grid) {
        int maxSum = int.MinValue;
        int m = grid.GetLength(0);
        int n = grid.GetLength(1);

        for (int i = 0; i < m - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                int sum = grid[i,j] + grid[i,j+1] + grid[i,j+2] +
                          grid[i+1,j+1] +
                          grid[i+2,j] + grid[i+2,j+1] + grid[i+2,j+2];
                maxSum = Math.Max(maxSum, sum);
            }
        }
        return maxSum;
    }

    public static void Main() {
        int[,] grid = {{6,2,1,3},{4,2,1,5},{9,2,8,7},{4,1,2,9}};
        Console.WriteLine("Maximum Hourglass Sum: " + MaxHourglassSum(grid));
    }
}

This Python code calculates the maximum sum of hourglass shapes in a matrix. It iterates over valid starting positions and computes sums as per the hourglass pattern.

Complexity

Time Complexity: O(m * n) because of nested loops through potential hourglass starts. Space Complexity: O(1) since it uses fixed variable space.

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.

def optimized_max_hourglass_sum(grid):
    max_sum = float('-inf')
    m = len(grid)
    n = len(grid[0])
    
    for i in range(m - 2):
        current_sum = (grid[i][0] + grid[i][1] + grid[i][2] +
                       grid[i+1][1] +
                       grid[i+2][0] + grid[i+2][1] + grid[i+2][2])
        max_sum = max(max_sum, current_sum)

        for j in range(n - 3):
            current_sum = current_sum - (grid[i][j] + grid[i+2][j]) +
                          (grid[i][j+3] + grid[i+2][j+3])
            current_sum = current_sum - grid[i+1][j+1] + grid[i+1][j+2]

            max_sum = max(max_sum, current_sum)

    return max_sum

grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]
print("Maximum Hourglass Sum:", optimized_max_hourglass_sum(grid))
public class Solution {
    public static int optimizedMaxHourglassSum(int[][] grid) {
        int maxSum = Integer.MIN_VALUE;
        int m = grid.length, n = grid[0].length;
        
        for (int i = 0; i < m - 2; i++) {
            int currentSum = grid[i][0] + grid[i][1] + grid[i][2]
                           + grid[i+1][1]
                           + grid[i+2][0] + grid[i+2][1] + grid[i+2][2];
            maxSum = Math.max(maxSum, currentSum);

            for (int j = 0; j < n - 3; j++) {
                currentSum = currentSum - (grid[i][j] + grid[i+2][j]) +
                             (grid[i][j+3] + grid[i+2][j+3]);
                currentSum = currentSum - grid[i+1][j+1] + grid[i+1][j+2];

                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[][] grid = {{6, 2, 1, 3}, {4, 2, 1, 5}, {9, 2, 8, 7}, {4, 1, 2, 9}};
        System.out.println("Maximum Hourglass Sum: " + optimizedMaxHourglassSum(grid));
    }
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int optimizedMaxHourglassSum(const vector<vector<int>>& grid) {
    int maxSum = INT_MIN;
    int m = grid.size();
    int n = grid[0].size();

    for (int i = 0; i < m - 2; i++) {
        int currentSum = grid[i][0] + grid[i][1] + grid[i][2] +
                         grid[i+1][1] +
                         grid[i+2][0] + grid[i+2][1] + grid[i+2][2];
        maxSum = max(maxSum, currentSum);

        for (int j = 0; j < n - 3; j++) {
            currentSum = currentSum - (grid[i][j] + grid[i+2][j]) +
                         (grid[i][j+3] + grid[i+2][j+3]);
            currentSum = currentSum - grid[i+1][j+1] + grid[i+1][j+2];

            maxSum = max(maxSum, currentSum);
        }
    }
    return maxSum;
}

int main() {
    vector<vector<int>> grid = {{6, 2, 1, 3}, {4, 2, 1, 5}, {9, 2, 8, 7}, {4, 1, 2, 9}};
    cout << "Maximum Hourglass Sum: " << optimizedMaxHourglassSum(grid);
    return 0;
}
function optimizedMaxHourglassSum(grid) {
    let maxSum = -Infinity;
    let m = grid.length;
    let n = grid[0].length;

    for (let i = 0; i < m - 2; i++) {
        let currentSum = grid[i][0] + grid[i][1] + grid[i][2] +
                         grid[i+1][1] +
                         grid[i+2][0] + grid[i+2][1] + grid[i+2][2];
        maxSum = Math.max(maxSum, currentSum);

        for (let j = 0; j < n - 3; j++) {
            currentSum = currentSum - (grid[i][j] + grid[i+2][j]) +
                         (grid[i][j+3] + grid[i+2][j+3]);
            currentSum = currentSum - grid[i+1][j+1] + grid[i+1][j+2];

            maxSum = Math.max(maxSum, currentSum);
        }
    }
    return maxSum;
}

let grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]];
console.log("Maximum Hourglass Sum:", optimizedMaxHourglassSum(grid));
#include <stdio.h>

int slidingWindowHourglassSum(int grid[][150], int m, int n) {
    int maxSum = 0;
    for (int i = 0; i < m - 2; i++) {
        int windowSum = 0;
        for (int j = 0; j < 3; j++)
            windowSum += grid[i][j] + grid[i + 2][j];
        windowSum += grid[i + 1][1];
        maxSum = windowSum;

        for (int j = 0; j < n - 3; j++) {
            windowSum = windowSum - grid[i][j] - grid[i+2][j] + grid[i][j+3] + grid[i+2][j+3];
            windowSum = windowSum - grid[i + 1][j + 1] + grid[i + 1][j + 2];
            if (windowSum > maxSum) maxSum = windowSum;
        }
    }
    return maxSum;
}

int main() {
    int grid[4][150] = {{6, 2, 1, 3}, {4, 2, 1, 5}, {9, 2, 8, 7}, {4, 1, 2, 9}};
    int maxSum = slidingWindowHourglassSum(grid, 4, 4);
    printf("Maximum Hourglass Sum: %d", maxSum);
    return 0;
}
using System;

class Solution {
    public static int OptimizedMaxHourglassSum(int[,] grid) {
        int maxSum = int.MinValue;
        int m = grid.GetLength(0);
        int n = grid.GetLength(1);

        for (int i = 0; i < m - 2; i++) {
            int currentSum = grid[i,0] + grid[i,1] + grid[i,2] +
                             grid[i+1,1] +
                             grid[i+2,0] + grid[i+2,1] + grid[i+2,2];
            maxSum = Math.Max(maxSum, currentSum);

            for (int j = 0; j < n - 3; j++) {
                currentSum = currentSum - (grid[i,j] + grid[i+2,j]) +
                             (grid[i,j+3] + grid[i+2,j+3]);
                currentSum = currentSum - grid[i+1,j+1] + grid[i+1,j+2];

                maxSum = Math.Max(maxSum, currentSum);
            }
        }
        return maxSum;
    }

    public static void Main() {
        int[,] grid = {{6,2,1,3},{4,2,1,5},{9,2,8,7},{4,1,2,9}};
        Console.WriteLine("Maximum Hourglass Sum: " + OptimizedMaxHourglassSum(grid));
    }
}

This Python solution improves by recalculating the hourglass sum on value changes as it slides over the matrix, improving calculation efficiency.

Complexity

Time Complexity: O(m * n) since it uses a more intelligent approach for adjustments. Space Complexity: O(1), using direct computations within fixed storage.

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

function maxSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    let ans = 0;
    for (let i = 1; i < m - 1; ++i) {
        for (let j = 1; j < n - 1; ++j) {
            let s = -grid[i][j - 1] - grid[i][j + 1];
            for (let x = i - 1; x <= i + 1; ++x) {
                for (let y = j - 1; y <= j + 1; ++y) {
                    s += grid[x][y];
                }
            }
            ans = Math.max(ans, s);
        }
    }
    return ans;
}
func maxSum(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	for i := 1; i < m-1; i++ {
		for j := 1; j < n-1; j++ {
			s := -grid[i][j-1] - grid[i][j+1]
			for x := i - 1; x <= i+1; x++ {
				for y := j - 1; y <= j+1; y++ {
					s += grid[x][y]
				}
			}
			ans = max(ans, s)
		}
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(m * n) because of nested loops through potential hourglass starts. Space Complexity: O(1) since it uses fixed variable space.

Optimized Sliding Window Approach

Time Complexity: O(m * n) since it uses a more intelligent approach for adjustments. Space Complexity: O(1), using direct computations within fixed storage.

Enumeration–

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.

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.

Comments

Next problem · similarMatrix Block SumMedium
Now write it yourselfClose this page and solve Maximum Sum of an Hourglass in the editor, without looking.
Practise Maximum Sum of an Hourglass