2D Array - Hourglass Sum

easy

arrays

Description

Given a 6x6 2D array, calculate the hourglass sum for every hourglass and return the maximum hourglass sum. An hourglass is a subset of values with indices falling in this pattern:

a b c
d
e f g

There are 16 hourglasses in a 6x6 array. The hourglass sum is the sum of the 7 values in an hourglass pattern.

Example 1:
Input: arr = [[1,1,1,0,0,0],[0,1,0,0,0,0],[1,1,1,0,0,0],[0,0,2,4,4,0],[0,0,0,2,0,0],[0,0,1,2,4,0]]
Output: 19
Explanation: The hourglass with maximum sum starts at row 3, col 2:
2 4 4
2
1 2 4
Sum = 2+4+4+2+1+2+4 = 19

Example 2:
Input: arr = [[-9,-9,-9,1,1,1],[0,-9,0,4,3,2],[-9,-9,-9,1,2,3],[0,0,8,6,6,0],[0,0,0,-2,0,0],[0,0,1,2,4,0]]
Output: 28
Explanation: The hourglass with maximum sum starts at row 1, col 3:
1 1 1
4
1 2 3
Sum = 1+1+1+4+1+2+3 = 13? Actually the max is at row 2, col 2:
0 4 3
1
8 6 6
Sum = 0+4+3+1+8+6+6 = 28

Constraints

Array is always 6x6
-9 <= arr[i][j] <= 9

Complexity

Show Complexity

Time: O(1)
Space: O(1)

Hints

Show Hints

Pattern: 2D array traversal with fixed pattern
Approach: For each valid top-left position (0-3, 0-3), calculate sum of 7 elements in hourglass pattern and track maximum
Complexity: Fixed 6x6 grid means constant time - iterate through all 16 hourglass positions

Solutions

Show PY Solution

# Setup formula
# row, col
# arr[row,   col]       ...        arr[row,   col+2]
#                arr[row+1, col+1]
# arr[row+2, col]       ...        arr[row+2, col+2]


def solution(arr):
    nrows = len(arr)

    answer = float("-inf")

    for row in range(nrows - 2):
        for col in range(len(arr[row]) - 2):
            # fmt: off
            s = arr[row][col]    +   arr[row][col+1]    +    arr[row][col+2]    + \
                                     arr[row+1][col+1]                          + \
                arr[row+2][col]  +   arr[row+2][col+1]  +    arr[row+2][col+2]
            # fmt: on
            answer = max(answer, s)

    return answer