We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Sum of an Hourglass

Number: 2508

Difficulty: Medium

Paid? No

Companies: Nutanix

Problem Description

Given an m x n grid of non-negative integers, find the hourglass with the maximum sum. An hourglass is defined by selecting 3 consecutive elements in the top row, the middle element of the second row (from the middle column), and 3 consecutive elements in the bottom row. The hourglass cannot be rotated and must be fully contained within the grid.

Key Insights

  • An hourglass has a fixed 3x3 shape with one element missing (the corners of the middle row).
  • We need to iterate over all valid hourglass starting positions ensuring the hourglass stays within the grid.
  • For each valid starting index (i, j), the hourglass sum is calculated as: grid[i][j] + grid[i][j+1] + grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2].
  • Given the constraints, a brute force approach that computes the sum for every possible hourglass is efficient enough.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the dimensions of the grid
Space Complexity: O(1) (apart from the input which is given)

Solution

The solution iterates through each possible top-left coordinate of an hourglass in the grid. For each coordinate (i, j), it computes the sum by adding the seven specific elements that form the hourglass. A variable is maintained to track the maximum sum seen so far. Once all possible hourglasses are evaluated, the maximum sum is returned.

The approach uses simple 2D array traversal with constant additional space. There are no advanced data structures required.

Code Solutions

# Python solution for Maximum Sum of an Hourglass

def max_hourglass_sum(grid):
    # Calculate the number of rows and columns
    m = len(grid)
    n = len(grid[0])
    
    # Initialize max_sum to the smallest possible value
    max_sum = 0
    
    # Iterate over all possible starting indices where an hourglass can fit
    for i in range(m - 2):
        for j in range(n - 2):
            # Calculate hourglass sum using defined indices
            hourglass_sum = (grid[i][j] + grid[i][j + 1] + grid[i][j + 2] +
                             grid[i + 1][j + 1] +
                             grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2])
            # Update max_sum if we have found a larger hourglass sum
            max_sum = max(max_sum, hourglass_sum)
    return max_sum

# Example usage:
# grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]
# print(max_hourglass_sum(grid))  # Output: 30
← Back to All Questions