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 themaximum sum of the elements of an hourglass.

Note that an hourglass cannot be rotated and must be entirely contained within the matrix.

Examples

Example 1

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2022/08/21/1.jpg)

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

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2022/08/21/2.jpg)

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] <= 10^6

Solution

Method 1 – Brute Force Traversal

Intuition

An hourglass in a matrix is a fixed 3x3 pattern. By iterating over all possible top-left positions of an hourglass, we can compute the sum for each and track the maximum. This works because the hourglass shape is always the same and must fit entirely within the matrix.

Approach

  1. For each cell (i, j) that can be the top-left of a 3x3 hourglass (i.e., i <= m-3, j <= n-3):
    • Calculate the sum of the hourglass:
      • Top row: grid[i][j] + grid[i][j+1] + grid[i][j+2]
      • Middle: grid[i+1][j+1]
      • Bottom row: grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2]
  2. Track the maximum sum found.
  3. Return the maximum sum.

Complexity

  • ⏰ Time complexity: O(mn) — Each cell is checked once, and hourglass sum is O(1).
  • 🧺 Space complexity: O(1) — Only a variable for the maximum sum is used.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int maxSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = INT_MIN;
        for (int i = 0; i + 2 < m; ++i) {
            for (int j = 0; j + 2 < n; ++j) {
                int s = 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];
                ans = max(ans, s);
            }
        }
        return ans;
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maxSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    ans := -1 << 31
    for i := 0; i+2 < m; i++ {
        for j := 0; j+2 < n; j++ {
            s := 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 s > ans { ans = s }
        }
    }
    return ans
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int maxSum(int[][] grid) {
        int m = grid.length, n = grid[0].length, ans = Integer.MIN_VALUE;
        for (int i = 0; i + 2 < m; ++i) {
            for (int j = 0; j + 2 < n; ++j) {
                int s = 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];
                ans = Math.max(ans, s);
            }
        }
        return ans;
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maxSum(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        var ans = Int.MIN_VALUE
        for (i in 0 until m - 2) {
            for (j in 0 until n - 2) {
                val s = 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]
                ans = maxOf(ans, s)
            }
        }
        return ans
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def max_sum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    ans = float('-inf')
    for i in range(m - 2):
        for j in range(n - 2):
            s = 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]
            ans = max(ans, s)
    return ans
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn max_sum(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = i32::MIN;
        for i in 0..m-2 {
            for j in 0..n-2 {
                let s = 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];
                ans = ans.max(s);
            }
        }
        ans
    }
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maxSum(grid: number[][]): number {
        const m = grid.length, n = grid[0].length;
        let ans = -Infinity;
        for (let i = 0; i + 2 < m; ++i) {
            for (let j = 0; j + 2 < n; ++j) {
                const s = 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];
                ans = Math.max(ans, s);
            }
        }
        return ans;
    }
}