Maximum Sum of an Hourglass

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.

Examples

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.

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

Code

C++

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

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

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

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

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

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

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;
    }
}