#2212Time: O(m*n). The pre-computation of the prefix sum array takes O(m*n), and iterating through all possible hourglasses also takes O(m*n).Space: O(m*n) to store the 2D prefix sum array.2 companies
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.length
n == grid[i].length
3 <= m, n <= 150
0 <= grid[i][j] <= 106
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a 2D prefix sum array to optimize the calculation of the sum of elements within any rectangular subgrid. An hourglass's sum can be derived by first calculating the sum of the 3x3 bounding box and then subtracting the two elements that are not part of the hourglass shape. While the time complexity is asymptotically the same as a direct approach, it incurs a significant space cost.
Algorithm
Get the dimensions m and n of the grid.
Create a prefixSum array of size (m+1) x (n+1) and initialize it with zeros. The type should be long to avoid overflow as the sum can be large.
Populate the prefixSum array. For each i from 0 to m-1 and j from 0 to n-1:
prefixSum[i+1][j+1] = grid[i][j] + prefixSum[i][j+1] + prefixSum[i+1][j] - prefixSum[i][j].
Initialize maxSum = 0.
Iterate r from 0 to m-3.
Inside, iterate c from 0 to n-3.
Calculate the sum of the 3x3 rectangle at (r, c) using the prefix sum array: rectSum = prefixSum[r+3][c+3] - prefixSum[r][c+3] - prefixSum[r+3][c] + prefixSum[r][c].
Calculate the hourglass sum by subtracting the two non-hourglass elements: currentSum = rectSum - grid[r+1][c] - grid[r+1][c+2].
Update maxSum = max(maxSum, currentSum).
Return maxSum.
Walkthrough
First, we pre-compute a 2D prefix sum array, let's call it prefixSum, of size (m+1) x (n+1). The cell prefixSum[i][j] stores the sum of all elements in the rectangle from (0, 0) to (i-1, j-1). This pre-computation takes O(m*n) time. The formula to populate this array is prefixSum[i+1][j+1] = grid[i][j] + prefixSum[i][j+1] + prefixSum[i+1][j] - prefixSum[i][j]. Note that a long data type is necessary for the prefix sum array to prevent integer overflow.
Once the prefixSum array is built, we iterate through all possible top-left corners (r, c) of an hourglass. For each corner, we can calculate the sum of the corresponding 3x3 rectangle in O(1) time. Then, we subtract the values of the two cells at grid[r+1][c] and grid[r+1][c+2] to get the actual hourglass sum. We keep track of the maximum sum found and return it after checking all possibilities.
1class Solution {2 public int maxSum(int[][] grid) {3 int m = grid.length;4 int n = grid[0].length;5 long[][] prefixSum = new long[m + 1][n + 1];67 for (int i = 0; i < m; i++) {8 for (int j = 0; j < n; j++) {9 prefixSum[i + 1][j + 1] = grid[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];10 }11 }1213 int maxSum = 0;14 for (int r = 0; r <= m - 3; r++) {15 for (int c = 0; c <= n - 3; c++) {16 // Sum of 3x3 rectangle starting at (r, c)17 long rectSum = prefixSum[r + 3][c + 3] - prefixSum[r][c + 3] - prefixSum[r + 3][c] + prefixSum[r][c];1819 // Subtract the two middle-row side elements20 long currentSum = rectSum - grid[r + 1][c] - grid[r + 1][c + 2];2122 maxSum = Math.max(maxSum, (int)currentSum);23 }24 }25 return maxSum;26 }27}
Complexity
Time
O(m*n). The pre-computation of the prefix sum array takes O(m*n), and iterating through all possible hourglasses also takes O(m*n).
Space
O(m*n) to store the 2D prefix sum array.
Trade-offs
Pros
Demonstrates a powerful technique (prefix sums) applicable to a wide range of sub-array/sub-matrix sum problems.
Once the prefix sum array is built, calculating the sum of any rectangle is an O(1) operation.
Cons
Requires O(m*n) extra space, which is worse than the direct iteration approach.
More complex to implement due to the pre-computation step.
The constant factor in the time complexity is higher, potentially making it slower in practice for this specific problem.
This is the most straightforward and optimal approach for this problem. It involves a direct simulation by iterating through every possible position where an hourglass can be formed within the grid. For each position, we calculate the sum of its seven elements and keep track of the maximum sum encountered.
Algorithm
Get the dimensions m (rows) and n (columns) of the grid.
Initialize a variable maxSum to 0. Since grid values are non-negative, the minimum possible sum is 0.
Use nested loops to iterate through every possible top-left corner (r, c) of an hourglass. The outer loop for r will go from 0 to m-3, and the inner loop for c will go from 0 to n-3.
Inside the loops, for each (r, c), directly calculate the sum of the 7 elements forming the hourglass:
Compare currentSum with maxSum and update maxSum if currentSum is greater: maxSum = Math.max(maxSum, currentSum).
After the loops complete, return maxSum.
Walkthrough
An hourglass is a 3x3 shape, so for it to be fully contained in the grid, its top-left corner (r, c) can be at any row r from 0 to m-3 and any column c from 0 to n-3. The algorithm simply uses two nested loops to traverse all these valid starting positions.
For each starting position (r, c), we perform a constant number of additions to sum up the 7 integer values that constitute the hourglass. This sum is then compared with a running maximum, maxSum, which is updated whenever a larger sum is found. Because we systematically check every single possible hourglass, we are guaranteed to find the one with the maximum sum. This method is highly efficient as it avoids any pre-computation and uses minimal extra memory.
1class Solution {2 public int maxSum(int[][] grid) {3 int m = grid.length;4 int n = grid[0].length;5 int maxSum = 0;67 // Iterate through all possible top-left corners of an hourglass8 for (int r = 0; r <= m - 3; r++) {9 for (int c = 0; c <= n - 3; c++) {10 // Calculate the sum of the current hourglass11 int currentSum = grid[r][c] + grid[r][c+1] + grid[r][c+2]12 + grid[r+1][c+1]13 + grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2];1415 // Update the maximum sum found so far16 maxSum = Math.max(maxSum, currentSum);17 }18 }19 return maxSum;20 }21}
Complexity
Time
O(m*n). The two nested loops run `(m-2) * (n-2)` times, and inside the loop, we perform a constant number of operations.
Space
O(1). Only a few variables are used for loop counters and storing the maximum sum, which is constant extra space.
Trade-offs
Pros
Optimal time complexity of O(m*n).
Optimal space complexity of O(1).
Very simple to understand and implement.
Generally faster in practice than the prefix sum approach due to lower constant factors and no overhead.
Cons
This specific implementation is tailored to the 3x3 hourglass shape and is not immediately generalizable to other shapes without modifying the summation logic.
Solutions
Solution
1class Solution {2public3 int maxSum(int[][] grid) {4 int m = grid.length, n = grid[0].length;5 int ans = 0;6 for (int i = 1; i < m - 1; ++i) {7 for (int j = 1; j < n - 1; ++j) {8 int s = -grid[i][j - 1] - grid[i][j + 1];9 for (int x = i - 1; x <= i + 1; ++x) {10 for (int y = j - 1; y <= j + 1; ++y) {11 s += grid[x][y];12 }13 }14 ans = Math.max(ans, s);15 }16 }17 return ans;18 }19}
1class Solution {2public:3 int maxSum(vector<vector<int>> &grid) {4 int m = grid.size(), n = grid[0].size();5 int ans = 0;6 for (int i = 1; i < m - 1; ++i) {7 for (int j = 1; j < n - 1; ++j) {8 int s = -grid[i][j - 1] - grid[i][j + 1];9 for (int x = i - 1; x <= i + 1; ++x) {10 for (int y = j - 1; y <= j + 1; ++y) {11 s += grid[x][y];12 }13 }14 ans = max(ans, s);15 }16 }17 return ans;18 }19};
1class Solution:2 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
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
