This is a problem from Hackerrank (https://www.hackerrank.com/challenges/2d-array/problem). We're given a 6x6 (always) 2D array and asked to compute the sums of all the hourglass patterns in the array. An hourglass pattern is of the shape
1 1 1
1
1 1 1
where the 1's form the hourglass. In this case the sum is 7, but it could be any integer from -63 to 63, the constraints being: -9 <= arr[i][j] <= 9
. There are 16 hourglasses in each 6x6 2D array, and we're asked to return the greatest hourglass value.
As an example, the following 2D array has a maximum hourglass value of 28:
-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
My code:
def hourglassSum(arr):
max_hourglass = -63
for column in range(len(arr)-2):
for row in range(len(arr)-2):
max_hourglass = max(arr[row][column] + arr[row][column+1] + arr[row][column+2] \
+ arr[row+1][column+1] + arr[row+2][column] + arr[row+2][column+1] \
+ arr[row+2][column+2], max_hourglass)
return max_hourglass
Is there any way to make this faster / more efficient? I'm reusing a lot of the same numbers in my calculations, which seems wasteful; is there a dynamic programming solution I'm not seeing, anything else? I appreciate any comments or optimization opportunities on my code, thank you.