Problem Solving: Hourglass

Below is a 6 X 6 2D array arr. In this question you are asked to identify hourglasses in the array.

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

There are 16 hourglasses in arr. An hourglass is a subset of values falling in this pattern:

a b c
  d
e f g

An hourglass sum is the sum of all an hourglass’s values.

Question:

Calculate all the hourglass sums in a 2D array. Return the maximum hourglass sum. The array will always be 6 X 6.

Solution:

Make int variables largestHourglassSum and currentHourglassSum. largestHourglassSum will be initialized as the first hourglass’s sum. currentHourglassSum will be the current hourglass’s sum as the loops iterate. The nested for loop will move through the array to capture and sum each new hourglass. As the loops iterate in the If statement if the currentHourglassSum is larger that will now become largestHourglassSum.

Hourglass 1: arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+1] + arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2]

Hourglass 2: Increment j and repeat the above.

Method:

    static int hourglassSum(int[][] arr) {
        int currentCount = 0;
    	int count = arr[0][0] + arr[0][1] + arr[0][2] 
                + arr[1][1] + arr[2][0] + arr[2][1] 
                + arr[2][2];
        
        for(int i = 0; i < arr.length-2; i++) {
            for (int j = 0; j < arr.length-2; j++) {
                currentCount = arr[i][j] + arr[i][j+1] + arr[i][j+2] 
                    + arr[i+1][j+1] + arr[i+2][j] + arr[i+2][j+1] 
                    + arr[i+2][j+2];
                if(currentCount > count) {
                    count = currentCount;
                }
            } 
        } return count;
    }

Accompanying test:

	@Test
	void whenGivenArray_shouldReturnHourglassSum() {
		//given
		Array2D array = new Array2D();
		//when
		int[][] arr = {	{-1, -1, 0, -9, -2, -2},
						{-2, -1, -6, -8, -2, -5},
						{-1, -1, -1, -2, -3, -4},
						{-1, -9, -2, -4, -4, -5},
						{-7, -3, -3, -2, -9, -9},
						{-1, -3, -1, -2, -4, -5}};
		//then
		Assertions.assertEquals(-6, array.hourglassSum(arr));
	}

I hope this is helpful, my GitHub is linked below with the problem we’ve just discussed. Problems sourced on HackerRank.

Emily Bowe on GitHub – 2D array