Maximum Sum of an Hourglass — Solution in Python, Java & C++
Maximum Sum of an Hourglass solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Sum of an Hourglass is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google, TCS and Nutanix interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Prefix Sum
- Asked at: Amazon, Google, TCS, Nutanix
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An hourglass in a matrix is a 3 × 3 window from which the middle-left and middle-right cells are removed — it keeps the whole top row of the window, its centre cell, and its whole bottom row (seven cells in all):
a b c
d
e f g
Given an m x n integer matrix grid, return the largest sum of the seven cells over every hourglass that fits entirely inside the grid. The hourglass cannot be rotated.
Example 1
Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 35
Explanation: The only hourglass is 1 + 2 + 3 + 5 + 7 + 8 + 9.
Example 2
Input: grid = [[3,1,4,1],[5,9,2,6],[5,3,5,8]]
Output: 30
Explanation: The left hourglass sums to 3 + 1 + 4 + 9 + 5 + 3 + 5 = 30; the right one to 24.
Example 3
Input: grid = [[0,0,0],[0,0,0],[0,0,0]]
Output: 0
Constraints
m == grid.lengthn == grid[i].length3 <= m, n <= 1500 <= grid[i][j] <= 10^6
Hints for Maximum Sum of an Hourglass
Hint 1
An hourglass is fixed by its top-left corner
(r, c), withr <= m - 3andc <= n - 3.Hint 2
Each hourglass has exactly seven cells, so summing them directly costs O(1).
Hint 3
Try every top-left corner and keep the maximum of the seven-cell sums.
How to solve Maximum Sum of an Hourglass
There are only (m - 2) × (n - 2) hourglasses and each has a constant seven cells, so enumerating them all is already optimal.
Approach
- For every top-left corner
(r, c)withr + 2 < mandc + 2 < n: - Add
grid[r][c..c+2],grid[r+1][c+1]andgrid[r+2][c..c+2]. - Keep the largest sum seen and return it.
Why it works
Every hourglass that fits is identified by exactly one top-left corner in that range, so the loop examines each one once and the maximum is exact.
Complexity
- Time —
O(m · n) - Space —
O(1)
Pitfalls
- The middle row contributes only its centre cell — not all three.
- Corners must stop at
m - 3andn - 3; going further reads outside the grid. - Seven values of up to 10^6 sum to 7 × 10^6, which fits comfortably in 32 bits.
Reference solution
Python
from typing import List
def maxSum(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
best = 0
for r in range(m - 2):
for c in range(n - 2):
s = sum(grid[r][c:c + 3]) + grid[r + 1][c + 1] + sum(grid[r + 2][c:c + 3])
if s > best:
best = s
return bestJava
public static int maxSum(int[][] grid) {
int m = grid.length, n = grid[0].length, best = 0;
for (int r = 0; r + 2 < m; r++) {
for (int c = 0; c + 2 < n; c++) {
int s = grid[r][c] + grid[r][c + 1] + grid[r][c + 2]
+ grid[r + 1][c + 1]
+ grid[r + 2][c] + grid[r + 2][c + 1] + grid[r + 2][c + 2];
if (s > best) best = s;
}
}
return best;
}C++
int maxSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), best = 0;
for (int r = 0; r + 2 < m; r++) {
for (int c = 0; c + 2 < n; c++) {
int s = grid[r][c] + grid[r][c + 1] + grid[r][c + 2]
+ grid[r + 1][c + 1]
+ grid[r + 2][c] + grid[r + 2][c + 1] + grid[r + 2][c + 2];
best = max(best, s);
}
}
return best;
}JavaScript
var maxSum = function(grid) {
var m = grid.length, n = grid[0].length, best = 0;
for (var r = 0; r + 2 < m; r++) {
for (var c = 0; c + 2 < n; c++) {
var s = grid[r][c] + grid[r][c + 1] + grid[r][c + 2]
+ grid[r + 1][c + 1]
+ grid[r + 2][c] + grid[r + 2][c + 1] + grid[r + 2][c + 2];
if (s > best) best = s;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal