Problem Description

You are given an m x n integer matrix called grid.

An hourglass is defined as a specific pattern within the matrix that looks like this:

• It consists of 7 elements arranged in a 3×3 area
• The top row has 3 elements
• The middle row has only 1 element (the center)
• The bottom row has 3 elements

Visually, an hourglass pattern includes the positions:

a b c
  d
e f g

Where a, b, c are the top row, d is the middle center element, and e, f, g are the bottom row.

Your task is to find the maximum sum of all possible hourglasses that can be formed within the given matrix.

Important constraints:

• An hourglass must be completely contained within the matrix boundaries
• An hourglass cannot be rotated - it must maintain the exact pattern shown above
• The matrix must be at least 3×3 to contain even one hourglass

For example, in a 3×3 matrix, there would be exactly one hourglass (the entire matrix forms the hourglass pattern). In larger matrices, you can find multiple hourglasses by sliding the 3×3 window across different positions.

The solution involves checking all possible positions where an hourglass can be placed (ensuring it doesn't go out of bounds), calculating the sum of the 7 elements that form each hourglass, and returning the maximum sum found.

Intuition

When we look at the hourglass pattern, we notice it's essentially a 3×3 grid with two specific positions removed - the middle-left and middle-right positions. This gives us a key insight: instead of trying to track complex patterns, we can think of each hourglass as being centered at a specific point.

The natural choice for the center is the middle element of the hourglass (the single element in the middle row). If we pick any position (i, j) as the center, then the hourglass extends one position in all four directions, forming the 3×3 area.

For a center at position (i, j), the hourglass includes:

• Top row: (i-1, j-1), (i-1, j), (i-1, j+1)
• Middle: just (i, j)
• Bottom row: (i+1, j-1), (i+1, j), (i+1, j+1)

This means we need at least one row above and below our center, and one column to the left and right. So valid centers can only be at positions where i ranges from 1 to m-2 and j ranges from 1 to n-2.

To calculate the sum efficiently, we can use a clever trick: first sum all 9 elements in the 3×3 grid centered at (i, j), then subtract the two elements we don't want (the middle-left (i, j-1) and middle-right (i, j+1)). This is simpler than individually adding the 7 specific positions.

By iterating through all valid center positions and calculating the hourglass sum at each position, we can keep track of the maximum sum encountered. This brute force approach works well since we need to check every possible hourglass anyway to ensure we find the maximum.

Learn more about Prefix Sum patterns.

Solution Approach

Following our intuition, we implement the enumeration approach by iterating through all valid center positions of potential hourglasses.

Step 1: Determine the boundaries First, we get the dimensions of the grid: m rows and n columns. Since an hourglass needs one row above and below its center, and one column to the left and right, valid centers can only be at positions where:

• Row index i ranges from 1 to m-2 (inclusive)
• Column index j ranges from 1 to n-2 (inclusive)

Step 2: Enumerate all valid centers We use nested loops to iterate through all valid center positions:

for i in range(1, m - 1):
    for j in range(1, n - 1):

Step 3: Calculate hourglass sum for each center For each center position (i, j), we calculate the sum using the optimization trick:

1. First, sum all 9 elements in the 3×3 grid centered at (i, j)
2. Then subtract the two unwanted elements: grid[i][j-1] and grid[i][j+1]

The implementation uses a nested list comprehension to sum the 3×3 grid:

s = sum(grid[x][y] for x in range(i - 1, i + 2) for y in range(j - 1, j + 2))

This iterates through rows from i-1 to i+1 and columns from j-1 to j+1.

Then we subtract the middle-left and middle-right elements:

s = -grid[i][j - 1] - grid[i][j + 1] + sum(...)

Step 4: Track the maximum We maintain a variable ans initialized to 0, and update it whenever we find a larger hourglass sum:

ans = max(ans, s)

Time Complexity: O(m × n) where we visit each potential center once, and for each center, we perform a constant amount of work (summing 9 elements).

Space Complexity: O(1) as we only use a few variables to track the current sum and maximum.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a 4×4 grid:

grid = [[1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
        [13, 14, 15, 16]]

Step 1: Identify valid center positions

Since we need one row above/below and one column left/right of each center, valid centers are at positions where:

• Row index i ranges from 1 to 2 (m=4, so 1 to m-2=2)
• Column index j ranges from 1 to 2 (n=4, so 1 to n-2=2)

This gives us 4 possible centers: (1,1), (1,2), (2,1), and (2,2).

Step 2: Calculate hourglass sum at center (1,1)

Center at position (1,1) with value 6:

The 3×3 grid:        The hourglass pattern:
[1,  2,  3]          [1,  2,  3]
[5,  6,  7]    →     [    6    ]
[9, 10, 11]          [9, 10, 11]

Calculate sum:

• Sum of all 9 elements: 1+2+3+5+6+7+9+10+11 = 54
• Subtract middle-left (5) and middle-right (7): 54 - 5 - 7 = 42
• Hourglass sum = 42

Step 3: Calculate hourglass sum at center (1,2)

Center at position (1,2) with value 7:

The 3×3 grid:        The hourglass pattern:
[2,  3,  4]          [2,  3,  4]
[6,  7,  8]    →     [    7    ]
[10, 11, 12]         [10, 11, 12]

Calculate sum:

• Sum of all 9 elements: 2+3+4+6+7+8+10+11+12 = 63
• Subtract middle-left (6) and middle-right (8): 63 - 6 - 8 = 49
• Hourglass sum = 49

Step 4: Calculate hourglass sum at center (2,1)

Center at position (2,1) with value 10:

The 3×3 grid:        The hourglass pattern:
[5,  6,  7]          [5,  6,  7]
[9,  10, 11]   →     [    10   ]
[13, 14, 15]         [13, 14, 15]

Calculate sum:

• Sum of all 9 elements: 5+6+7+9+10+11+13+14+15 = 90
• Subtract middle-left (9) and middle-right (11): 90 - 9 - 11 = 70
• Hourglass sum = 70

Step 5: Calculate hourglass sum at center (2,2)

Center at position (2,2) with value 11:

The 3×3 grid:        The hourglass pattern:
[6,  7,  8]          [6,  7,  8]
[10, 11, 12]   →     [    11   ]
[14, 15, 16]         [14, 15, 16]

Calculate sum:

• Sum of all 9 elements: 6+7+8+10+11+12+14+15+16 = 99
• Subtract middle-left (10) and middle-right (12): 99 - 10 - 12 = 77
• Hourglass sum = 77

Step 6: Find the maximum

Comparing all hourglass sums: 42, 49, 70, 77

The maximum hourglass sum is 77.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n × 9) which simplifies to O(m × n), where m and n are the number of rows and columns of the matrix, respectively.

The algorithm uses two nested loops that iterate through positions (i, j) where i ranges from 1 to m-2 and j ranges from 1 to n-2, giving us approximately (m-2) × (n-2) iterations. For each position, the code computes the sum of a 3×3 grid centered at (i, j). The sum computation involves iterating through 9 cells (from i-1 to i+1 and j-1 to j+2), which is a constant operation. Since we perform a constant amount of work (9 cell accesses and additions) for each of the O(m × n) positions, the overall time complexity is O(m × n).

The space complexity is O(1) as the algorithm only uses a fixed number of variables (m, n, ans, i, j, s, and the iterator variables x and y in the generator expression) regardless of the input size. The generator expression doesn't create an intermediate list but computes the sum on-the-fly, maintaining constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initialization of Maximum Value

One of the most common mistakes is initializing the maximum sum to 0:

max_hourglass_sum = 0  # WRONG!

Why it's wrong: The grid can contain negative numbers. If all possible hourglass sums are negative, initializing to 0 will incorrectly return 0 instead of the actual maximum (negative) sum.

Example scenario:

grid = [[-5, -5, -5],
        [-5, -5, -5],
        [-5, -5, -5]]

The only hourglass sum would be -35, but the code would return 0.

Solution: Initialize to negative infinity or to the sum of the first valid hourglass:

# Option 1: Use negative infinity
max_hourglass_sum = float('-inf')

# Option 2: Calculate first hourglass sum as initial value
max_hourglass_sum = None
for center_row in range(1, rows - 1):
    for center_col in range(1, cols - 1):
        hourglass_sum = # ... calculate sum
        if max_hourglass_sum is None:
            max_hourglass_sum = hourglass_sum
        else:
            max_hourglass_sum = max(max_hourglass_sum, hourglass_sum)

2. Off-by-One Errors in Boundary Checking

Another frequent mistake is using incorrect loop boundaries:

# WRONG: This misses the last valid centers
for center_row in range(1, rows - 2):  
    for center_col in range(1, cols - 2):

# WRONG: This goes out of bounds
for center_row in range(1, rows):
    for center_col in range(1, cols):

Solution: Remember that for a center at (i, j), you need:

• Row i-1 (above) and row i+1 (below) to be valid
• Column j-1 (left) and column j+1 (right) to be valid

Therefore, valid ranges are range(1, rows - 1) and range(1, cols - 1).

3. Misunderstanding the Hourglass Pattern

Some might accidentally include or exclude wrong cells:

# WRONG: Including all 9 cells (forms a square, not hourglass)
hourglass_sum = sum(
    grid[row][col] 
    for row in range(center_row - 1, center_row + 2) 
    for col in range(center_col - 1, center_col + 2)
)
# Forgot to subtract the middle-left and middle-right cells!

Solution: Always remember the hourglass pattern excludes exactly 2 cells from the 3×3 grid - the middle-left and middle-right positions. Double-check by counting: an hourglass has exactly 7 cells, not 9.