How To Solve The 2D-Array Hourglass Code Challenge
How To Solve HackerRank’s 2D Array Hourglass Code Challenge With JavaScript
Problem
Breaking down the challenge into blocks of requirements, we get:
- Link to challenge: HackerRank’s 2D Array DS Code Challenge
- arr[i][j] = multi-dimensional array that is 6 x 6
- i = height of the array, with a number range of 0 to 5
- j = width of the array, with a number range of 0 to 5
- hourglass = the same of shape as a ( I) ⏳
- hourglass = 3 index values at the top, one in the middles, and 3 at the bottom
// Example 1
// arr[i][j] =
// [
// [ 1, 1, 1, 0, 0, 0 ],
// [ 0, 1, 0, 0, 0, 0 ],
// [ 1, 1, 1, 0, 0, 0 ],
// [ 0, 0, 2, 4, 4, 0 ],
// [ 0, 0, 0, 2, 0, 0 ],
// [ 0, 0, 1, 2, 4, 0 ]
// ]// an hourglass might look like
// 1 1 1
// 1
// 1 1 1
// or
// arr[0][0], a[0][1], a[0][2]
// a[1][1]
// arr[2][0], a[2][1], a[2][2]// The sum of this first hourglass is 7
All hour glass combinations:
1 1 1 1 1 0 1 0 0 0 0 0
1 0 0 0
1 1 1 1 1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0
1 1 0 0
0 0 2 0 2 4 2 4 4 4 4 01 1 1 1 1 0 1 0 0 0 0 0
0 2 4 4
0 0 0 0 0 2 0 2 0 2 0 00 0 2 0 2 4 2 4 4 4 4 0
0 0 2 0
0 0 1 0 1 2 1 2 4 2 4 0
The sum of each hourglass from left to right, top to bottom:
7 4 2 04 8 10 83 6 7 63 9 19 14
The larges value of all the hourglasses:
19
Goal
Write a function or functions that returns the largest summed number of all the hourglass patterns found in (ar)
Covering Our Bases
Our first step is to make sure we are getting the right formatted (arr). We need to cover the following:
- arr = array
- arr has a length of 6
- for each arr[i] has a length of 6
- arr[i][j] = 36 total values
function hourglassSum(arr) {
// default value returned
let hourglasses = []; // validating the arr
if (typeof arr === "object"
&& arr.length === 6
&& arr.map(i => i.length).reduce((p, n) => p + n) === 36)
{
// continue
}
// default returned value
// Math.max used to find the highest value in an array
return (hourglasses.length > 0) ? Math.max(...hourglasses) : 0;
}
Understanding The Problem
Next we need to understand that we can see a pattern with the hourglass. It takes up 3 spots at the top, continues to grab the next 3 until it reaches the last 3 values of the first column ( arr[0] ).
Traversing Columns And Rows
// Going left to right 1, 1, 1, 0, 0, 0 1, 1, 1, 0, 0, 0 1, 1, 1, 0, 0, 0
0, 1, 0, 0, 0, 0 0, 1, 0, 0, 0, 0 0, 1, 0, 0, 0, 0
1, 1, 1, 0, 0, 0 1, 1, 1, 0, 0, 0 1, 1, 1, 0, 0, 0
0, 0, 2, 4, 4, 0 0, 0, 2, 4, 4, 0 0, 0, 2, 4, 4, 0
0, 0, 0, 2, 0, 0 0, 0, 0, 2, 0, 0 0, 0, 0, 2, 0, 0
0, 0, 1, 2, 4, 0 0, 0, 1, 2, 4, 0 0, 0, 1, 2, 4, 01, 1, 1, 0, 0, 0
0, 1, 0, 0, 0, 0
1, 1, 1, 0, 0, 0
0, 0, 2, 4, 4, 0
0, 0, 0, 2, 0, 0
0, 0, 1, 2, 4, 0 // Starts back at one horizontally1, 1, 1, 0, 0, 0
0, 1, 0, 0, 0, 0
1, 1, 1, 0, 0, 0
0, 0, 2, 4, 4, 0
0, 0, 0, 2, 0, 0
0, 0, 1, 2, 4, 0 ....
And because this is a multi-dimensional array that requires going through its rows and columns, we can assume that we’ll be traversing it both from its row and column, which means two for loops.
for (let row = 0; row <= 3; row++) {
for (let col = 0; col <= 3; col++) {
// arr[row][col]
// ex: arr[3][2] = 2 from Example 1
}
}
We can also notice that vertical the hourglass pattern follows the same limits as it does horizontally by only taking 3, up until the last 3.
Finding The Pattern
Next we need to define the shape of the hourglass and see how we can define a formula for it.
1, 1, 1, 0, 0, 0
0, 1, 0, 0, 0, 0
1, 1, 1, 0, 0, 0
0, 0, 2, 4, 4, 0
0, 0, 0, 2, 0, 0
0, 0, 1, 2, 4, 0// First hourglass is
arr[0][0] // 1 - top left
arr[0][1] // 1 - top middle
arr[0][2] // 1 - top right
arr[1][1] // 1 - middle middle
arr[2][0] // 1 - bottom left
arr[2][1] // 1 - bottom middle
arr[2][2] // 1 - bottom right1, 1, 1, 0, 0, 0
0, 1, 0, 0, 0, 0
1, 1, 1, 0, 0, 0
0, 0, 2, 4, 4, 0
0, 0, 0, 2, 0, 0
0, 0, 1, 2, 4, 0// Second hourglass is
arr[0][1] // 1 - top left
arr[0][2] // 1 - top middle
arr[0][3] // 0 - top right
arr[1][2] // 0 - middle middle
arr[2][1] // 1 - bottom left
arr[2][2] // 1 - bottom middle
arr[2][3] // 0 - bottom right
If we replace the for index of arr[i] with our row variable we can decipher it to get the incremental value from the two for loops.
1, 1, 1, 0, 0, 0
0, 1, 0, 0, 0, 0
1, 1, 1, 0, 0, 0
0, 0, 2, 4, 4, 0
0, 0, 0, 2, 0, 0
0, 0, 1, 2, 4, 0// if row = 0 from our for loop// First hourglass is
arr[row][0] // 1 - top left
arr[row][1] // 1 - top middle
arr[row][2] // 1 - top right
arr[row + 1][1] // 1 - middle middle
arr[row + 2][0] // 1 - bottom left
arr[row + 2][1] // 1 - bottom middle
arr[row + 2][2] // 1 - bottom right
If we do the same and replace the for index of arr[i][j] with our col variable.
1, 1, 1, 0, 0, 0
0, 1, 0, 0, 0, 0
1, 1, 1, 0, 0, 0
0, 0, 2, 4, 4, 0
0, 0, 0, 2, 0, 0
0, 0, 1, 2, 4, 0// row = 0 from our for loop
// col = 0 from our for loop
// First hourglass is
arr[row][col] // 1 - top left
arr[row][col + 1] // 1 - top middle
arr[row][col + 2] // 1 - top right
arr[row + 1][col + 1] // 1 - middle middle
arr[row + 2][col] // 1 - bottom left
arr[row + 2][col + 1] // 1 - bottom middle
arr[row + 2][col + 2] // 1 - bottom right
Getting The Sum
Great, now we have the shape, now we just need to store all the values.
for (let row = 0; row <= 3; row++) {
for (let col = 0; col <= 3; col++) {
let sum = 0;
sum += arr[row][col];
sum += arr[row][col + 1];
sum += arr[row][col + 2];
sum += arr[row + 1][col + 1];
sum += arr[row + 2][col];
sum += arr[row + 2][col + 1];
sum += arr[row + 2][col + 2];
// First hourglass
// sum = 7
}
}
Storing The Values
Next we’ll want to add this value to our original hourglasses array so that when find the max value with Math.max, we can return it.
for (let row = 0; row <= 3; row++) {
for (let col = 0; col <= 3; col++) {
let sum = 0;
sum += arr[row][col];
sum += arr[row][col + 1];
sum += arr[row][col + 2];
sum += arr[row + 1][col + 1];
sum += arr[row + 2][col];
sum += arr[row + 2][col + 1];
sum += arr[row + 2][col + 2];
hourglasses.push(sum);
}
}
Solution
Putting the full solution together we get the following:
function hourglassSum(arr) {
let hourglasses = [];
if (typeof arr === "object"
&& arr.length === 6
&& arr.map(i => i.length).reduce((p, n) => p + n) === 36)
{
for (let row = 0; row <= 3; row++) {
for (let col = 0; col <= 3; col++) {
let sum = 0;
sum += arr[row][col];
sum += arr[row][col + 1];
sum += arr[row][col + 2];
sum += arr[row + 1][col + 1];
sum += arr[row + 2][col];
sum += arr[row + 2][col + 1];
sum += arr[row + 2][col + 2];
hourglasses.push(sum);
}
}
}
return (hourglasses.length > 0) ? Math.max(...hourglasses) : 0;
}
Test Cases
Now let’s validate the answer with some tests.
// test1[i][j] =
// 1, 1, 1, 0, 0, 0
// 0, 1, 0, 0, 0, 0
// 1, 1, 1, 0, 0, 0
// 0, 0, 2, 4, 4, 0
// 0, 0, 0, 2, 0, 0
// 0, 0, 1, 2, 4, 0
// Expected 19// test2[i][j] =
// 1, 1, 1, 0, 0, 0
// 0, 1, 0, 0, 0, 0
// 1, 1, 1, 0, 0, 0
// 0, 9, 2,-4,-4, 0
// 0, 0, 0,-2, 0, 0
// 0, 0,-1,-2,-4, 0
// Expected 13// test3[i][j] =
//-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
// Expected 28
// test4[i][j] =
// 0, 0, 1
// 1, 1, 1
// 3, 4, 5
// Expected 0hourglassSum(test1); // 19 ✅
hourglassSum(test2); // 13 ✅
hourglassSum(test3); // 28 ✅
hourglassSum(test4); // 0 ✅
Feedback!
If you have any recommendations on how this can be implemented better or talk about coding I would love to talk.
If you got value from this, please share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏
Please also follow me on twitter: @codingwithmanny and instagram at @codingwithmanny.