# Computing sums of weird pattern in 2D array as efficiently as possible

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.

Drat. My super pretty NumPy solution which is probably efficient doesn't get accepted because HackerRank apparently doesn't support NumPy here. Oh well, here it is anyway, maybe interesting/amusing for someone.

import sys
import numpy as np

h = a[0:4, 0:4] + a[0:4, 1:5] + a[0:4, 2:6]     + \
a[1:5, 1:5]                   + \
a[2:6, 0:4] + a[2:6, 1:5] + a[2:6, 2:6]

print(h.max())


Or with less code repetition:

import sys
import numpy as np

i, j, k = (slice(i, i+4) for i in range(3))

h = a[i,i] + a[i,j] + a[i,k]     + \
a[j,j]              + \
a[k,i] + a[k,j] + a[k,k]

print(h.max())


The 4x4 submatrix a[0:4, 0:4] contains the top-left value for each of the 16 hourglasses, a[0:4, 1:5] contains the top-middle value for each of the 16 hourglasses, etc. So adding them computes a 4x4 matrix containing the 16 hourglass sums.

• @Emma LeetCode does, and HackerRank does have a NumPy section Oct 16 '20 at 19:15
• Could you explain what it's doing? Does numpy loop automatically over the entire matrix? Oct 16 '20 at 20:27
• @jeremyradcliff Kinda, yes. I mean, a[0:4, 0:4] for example is the top-left 4x4 submatrix. That holds the top-left value for each of the 16 hourglasses. And a[0:4, 1:5] holds the top-middle value for each of the 16 hourglasses. And so on. What I do is I get those seven 4x4 submatrices and have NumPy add them for me (NumPy does the looping required for that). So I'm building all 16 hourglass sums at the same time, at NumPy speed. Oct 17 '20 at 1:25
• That's incredible. Thanks for explaining, I'm going to play with it today and try to integrate it Oct 17 '20 at 21:31