Maximum Sum of an Hourglass

Medium
1550.

Maximum Sum of an Hourglass

Maximum Sum of an Hourglass is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google, TCS and Nutanix interviews.

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.length
  • n == grid[i].length
  • 3 <= m, n <= 150
  • 0 <= grid[i][j] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxSum = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Maximum Sum of an Hourglass

  1. Hint 1

    An hourglass is fixed by its top-left corner (r, c), with r <= m - 3 and c <= n - 3.

  2. Hint 2

    Each hourglass has exactly seven cells, so summing them directly costs O(1).

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

  1. For every top-left corner (r, c) with r + 2 < m and c + 2 < n:
  2. Add grid[r][c..c+2], grid[r+1][c+1] and grid[r+2][c..c+2].
  3. 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 - 3 and n - 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 best

Java

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