Maximum Sum of an Hourglass — LeetCode 2428 Python Solution

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.

Example

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.

Python solution

class Solution:
    def maxSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                s = -grid[i][j - 1] - grid[i][j + 1]
                s += sum(
                    grid[x][y] for x in range(i - 1, i + 2) for y in range(j - 1, j + 2)
                )
                ans = max(ans, s)
        return ans

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2428. Maximum Sum of an Hourglass is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems