# Maximum Sum of an Hourglass
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-sum-of-an-hourglass)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-of-an-hourglass
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix), [Zoho](https://scaleengineer.com/companies/zoho)
---
## 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:

![](https://assets.glich.co/dsa/maximum-sum-of-an-hourglass/image0.jpg) 

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:**

![](https://assets.glich.co/dsa/maximum-sum-of-an-hourglass/image1.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:**

![](https://assets.glich.co/dsa/maximum-sum-of-an-hourglass/image2.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] <= 106`

# Approaches
## Using 2D Prefix Sums
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int maxSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        long[][] prefixSum = new long[m + 1][n + 1];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i + 1][j + 1] = grid[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];
            }
        }

        int maxSum = 0;
        for (int r = 0; r <= m - 3; r++) {
            for (int c = 0; c <= n - 3; c++) {
                // Sum of 3x3 rectangle starting at (r, c)
                long rectSum = prefixSum[r + 3][c + 3] - prefixSum[r][c + 3] - prefixSum[r + 3][c] + prefixSum[r][c];
                
                // Subtract the two middle-row side elements
                long currentSum = rectSum - grid[r + 1][c] - grid[r + 1][c + 2];
                
                maxSum = Math.max(maxSum, (int)currentSum);
            }
        }
        return maxSum;
    }
}
```
### Algorithm
1. Get the dimensions `m` and `n` of the `grid`.
2. 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.
3. 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]`.
4. Initialize `maxSum = 0`.
5. Iterate `r` from `0` to `m-3`.
6. Inside, iterate `c` from `0` to `n-3`.
7. 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]`.
8. Calculate the hourglass sum by subtracting the two non-hourglass elements: `currentSum = rectSum - grid[r+1][c] - grid[r+1][c+2]`.
9. Update `maxSum = max(maxSum, currentSum)`.
10. Return `maxSum`.

## Direct Iteration and Summation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int maxSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int maxSum = 0;

        // Iterate through all possible top-left corners of an hourglass
        for (int r = 0; r <= m - 3; r++) {
            for (int c = 0; c <= n - 3; c++) {
                // Calculate the sum of the current hourglass
                int currentSum = grid[r][c] + grid[r][c+1] + grid[r][c+2]
                               + grid[r+1][c+1]
                               + grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2];
                
                // Update the maximum sum found so far
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
}
```
### Algorithm
1. Get the dimensions `m` (rows) and `n` (columns) of the `grid`.
2. Initialize a variable `maxSum` to 0. Since grid values are non-negative, the minimum possible sum is 0.
3. 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`.
4. Inside the loops, for each `(r, c)`, directly calculate the sum of the 7 elements forming the hourglass:
   `currentSum = grid[r][c] + grid[r][c+1] + grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2]`.
5. Compare `currentSum` with `maxSum` and update `maxSum` if `currentSum` is greater: `maxSum = Math.max(maxSum, currentSum)`.
6. After the loops complete, return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int maxSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int ans = 0;
    for (int i = 1; i < m - 1; ++i) {
      for (int j = 1; j < n - 1; ++j) {
        int s = -grid[i][j - 1] - grid[i][j + 1];
        for (int x = i - 1; x <= i + 1; ++x) {
          for (int y = j - 1; y <= j + 1; ++y) {
            s += grid[x][y];
          }
        }
        ans = Math.max(ans, s);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSum(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int ans = 0;
    for (int i = 1; i < m - 1; ++i) {
      for (int j = 1; j < n - 1; ++j) {
        int s = -grid[i][j - 1] - grid[i][j + 1];
        for (int x = i - 1; x <= i + 1; ++x) {
          for (int y = j - 1; y <= j + 1; ++y) {
            s += grid[x][y];
          }
        }
        ans = max(ans, s);
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```