How do you solve Maximum Sum of an Hourglass on LeetCode?

Maximum Sum of an Hourglass (LeetCode #2428) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: Each hourglass is defined by a unique 3x3 submatrix.

What is the brute force solution for Maximum Sum of an Hourglass?

The brute force approach for Maximum Sum of an Hourglass is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible hourglass in the matrix and calculating their sums. This is straightforward but can be slow for larger matrices. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Maximum Sum of an Hourglass?

Maximum Sum of an Hourglass uses the following concepts: Array, Matrix, Prefix Sum. The recommended patterns to study are: Array, Matrix.

What are the interview tips for Maximum Sum of an Hourglass?

Always clarify the problem statement and constraints. Discuss your thought process and approach before coding. Consider edge cases, like the smallest possible matrix.

What are common mistakes when solving Maximum Sum of an Hourglass?

Forgetting to check bounds when accessing elements. Not initializing the maximum sum variable correctly.

#2428

Maximum Sum of an Hourglass

Medium

ArrayMatrixPrefix SumArrayMatrix

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution is essentially the same as the brute force approach but focuses on minimizing redundant calculations. We still check every hourglass, but we ensure that our calculations are efficient.

⚙️

Algorithm

3 steps

1Step 1: Initialize a variable to store the maximum hourglass sum.
2Step 2: Loop through the grid, ensuring to stay within bounds for hourglass formation.
3Step 3: Calculate the hourglass sum directly and update the maximum sum accordingly.

solution.py14 lines

1# Full working Python code
2
3def max_hourglass_sum(grid):
4    max_sum = float('-inf')
5    for i in range(len(grid) - 2):
6        for j in range(len(grid[0]) - 2):
7            hourglass_sum = (grid[i][j] + grid[i][j+1] + grid[i][j+2] +
8                             grid[i+1][j+1] +
9                             grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2])
10            max_sum = max(max_sum, hourglass_sum)
11    return max_sum
12
13# Example usage
14print(max_hourglass_sum([[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]))

ℹ

Complexity note: The time complexity remains O(n²) as we still iterate through the grid to check for hourglass sums. The space complexity is O(1) since we are only using a few variables to store sums and maximum values.

1Each hourglass is defined by a unique 3x3 submatrix.
2The center of the hourglass is always the middle element of the 3x3 submatrix.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.