Algorithms
HackerRank 2D Array - DS
HackerRank’s 2D Array Hourglass Code Challenge With JavaScript
Adam
The details for the problem detailed in this post can be found at https://www.hackerrank.com/challenges/2d-array/problem
The following solution is written in Javascript.
Problem
Breaking down the challenge into blocks of requirements, we get:
- 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 ⏳
- hourglass = 3 index values at the top, one in the middles, and 3 at the bottom
So we are given a two dimensional array consists of n rows and m columns and has a integers in a range -9 to 9 on each indexes. The task is to find maximum sum of values in a abstract hourglass shape.
The problem begins with a 6x6 2D Array, like this one:
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 in A is a subset of values with indices falling in the pattern below:
a b c
d
e f g
This hourglass pattern occurs 16 times within the array. Given the example above all the hour glass combinations would be:
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 0
1 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 0
0 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
Again using the sample data above the sum of each hourglass would be:
7 4 2 0
4 8 10 8
3 6 7 6
3 9 19 14
The largest value of all the hourglasses is:
19
Goal
The goal is to write a function that calculates the sum of the numbers in each of the hourglass patterns and return the maximum sum.
Constraints & Validation
Since the minimum value of any position is -9, the minimum value of the sum is -63.
function hourglassSum(arr) {
let max = -63;
}
Validating the arr
So we need to validate the following:
- The argument is an array
- Each of the 6 lines of inputs arr[i] contains 6 space-seperated integers arr[i][j]
function hourglassSum(arr) {
let max = -63;
if (Array.isArray(arr)
&& arr.length === 6
&& arr.map(i => i.length).reduce((p, n) => p + n) === 36)
{
// Loop through arr
}
return max;
}
Solution
We’ll use a nested loop to evaluate the sums of all the hourglass patterns (4 on each row) for all the possible rows (4 rows).
After each sum is computed, it will be compared to the current maximum sum and will replace that sum if it is greater.
Finally, after all iterations are complete, the maximum sum will be returned.
Here’s the completed function:
function hourglassSum(arr) {
let max = -63
if (Array.isArray(arr)
&& arr.length === 6
&& arr.map(i => i.length).reduce((p, n) => p + n) === 36) {
for (let row = 0; row < 4; row++) {
for (let col = 0; col < 4; 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];
max = max < sum ? sum : max;
}
}
}
return max;
}
Refactored Solution
function hourglassSum(arr) {
let max = -63;
if (Array.isArray(arr)
&& arr.length === 6
&& arr.map(i => i.length).reduce((p, n) => p + n) === 36) {
for (let i = 0; i < 4; i++) {
for (let j = 0; j < 4; j++) {
let sum = 0;
sum = (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]);
max = max < sum ? sum : max;
}
}
}
return max;
}