DEV Community 👩‍💻👨‍💻

Cover image for Hourglass Problem
sndp
sndp

Posted on • Updated on

Hourglass Problem

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
Enter fullscreen mode Exit fullscreen mode

And if you notice, there is hourglass shaped numbers.
The first one is below.

1 1 1
  1
1 1 1
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

You need to find the maximum sum of hourglass looking numbers.

Some hourglasses

In this I have circled some hourglass looking numbers.

Sum of Red hourglass is
(-9 + -9 + -9) + (-9) + (-9 + -9 + -9) = -63

Sum of Red hourglass

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
Enter fullscreen mode Exit fullscreen mode

The maximum hourglass is below. It's sum is 28

Sum of maximum

So How do we calculate the maximum of the hourglass looking numbers ?

You should follow these steps.

  1. Loop through each index of the array.
  2. Find the hourglass sum of the each regional hourglass.
  3. If the current sum is higher than the previous, maximum = current.
  4. 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

https://github.com/lizardkingLK/hourglass_problem

Top comments (0)

Thank you.

 
Thanks for visiting DEV, we’ve worked really hard to cultivate this great community and would love to have you join us. If you’d like to create an account, you can sign up here.