Watch 10 video solutions for Maximum Sum of an Hourglass, a medium level problem involving Array, Matrix, Prefix Sum. This walkthrough by NeetCode has 605,143 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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.
Constraints:
m == grid.lengthn == grid[i].length3 <= m, n <= 1500 <= grid[i][j] <= 106