This problem is based on a challenge on hackerrank. It is a bit tricky beginner level problem.
The problem is to find the maximum of all the hourglass shaped number sums in a given 2d integer array
A 6 x 6 array (2d) is given.
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
And if you notice, there is hourglass shaped numbers.
The first one is below.
1 1 1
1
1 1 1
The sum of this hourglass is (1 + 1 + 1) + (1) + (1 + 1 + 1) = 7
7 being the largest.
So now to the problem. You are given the below 2d array.
-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
You need to find the maximum sum of hourglass looking numbers.
In this I have circled some hourglass looking numbers.
Sum of Red hourglass is
(-9 + -9 + -9) + (-9) + (-9 + -9 + -9) = -63
And the rest of hourglass sums are like below
-63, -34, -9, 12,
-10, 0, 28, 23,
-27, -11, -2, 10,
9, 17, 25, 18
The maximum hourglass is below. It's sum is 28
So How do we calculate the maximum of the hourglass looking numbers ?
You should follow these steps.
- Loop through each index of the array.
- Find the hourglass sum of the each regional hourglass.
- If the current sum is higher than the previous, maximum = current.
- Print the maximum.
Starting from the first row first column is the index (0, 0). It contains the hourglass below.
-9 -9 -9
-9
-9 -9 -9
So you need to find the sum of this hourglass using another nested loop.
Then the second hourglass is in the index of (0, 1). It contains the hourglass below.
-9 -9 1
-9 0 4
-9 -9 1
Sum is calculated in this second one too.
If the second is higher than the first you can assign the maximum as the second sum. This is repeated until the end.
But we should not need to go until the last element since at (0, 4) index and indexes after that we can't make a hourglass shaped numbers.
And also for the row-wise it is invalid to go for (4, 0) index since hourglasses not shaped in thereafter.
Find the source code using below link
Top comments (0)