This blog post is based on the HackerRank Interview Preparation Kit 2D Array – DS question. HackerRank provides programming challenges that can be solved in the web browser in a variety of programming languages, and give real-time feedback on your solution’s success.
HackerRank Problem – 2 Dimensional Array Hourglass
Given a 6 x 6 2D Array, arr:
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
An hourglass in A is a subset of values with indices falling in this pattern in arr‘s graphical representation:
a b c d e f g
There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass’ values. Calculate the hourglass sum for every hourglass in arr, then print the maximum hourglass sum. The array will always be 6 x 6.
HackerRank Example
-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
The hourglass sums are:
-63, -34, -9, 12, -10, 0, 28, 23, -27, -11, -2, 10, 9, 17, 25, 18
The highest hourglass sum is from the hourglass beginning at row , column :
0 4 3 1 8 6 6
Function Description
Complete the function hourglassSum in the editor below.
hourglassSum has the following parameter(s):
- int arr[6][6]: an array of integers
Returns
- int: the maximum hourglass sum
Input Format
Each of the 6 lines of inputs arr[i] contains 6 space-separated integers arr[i][j].
Constraints
- -9 <= arr[i][j] <= 9
- 0 <= i,i <= 5
Output Format
Print the largest (maximum) hourglass sum found in .
Sample Input
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
Sample Output
19
Explanation
contains the following hourglasses:
The hourglass with the maximum sum () is:
2 4 4 2 1 2 4
Method to Complete
class Result
{
/*
* Complete the 'hourglassSum' function below.
*
* The function is expected to return an INTEGER.
* The function accepts 2D_INTEGER_ARRAY arr as parameter.
*/
public static int hourglassSum(List<List<int>> arr)
{
}
}
Understanding the Problem’s Founding Data Structure
At times, these HackerRank questions can seem incredibly intimidating, especially if there is a notation that you have not seen before.
It can be helpful to ground your understanding of the HackerRank question by thinking of data structures that relate specifically to .Net, starting simple and then building your way up. This often takes away the “magic” or ambiguity of the question.
What is a 6 x 6 2D array?
Firstly, an array is a .Net collection data structure.
var array = new int[] { 1, 1, 1, 0, 0, 0 };
This array has been initialised to contain 6 integers. Each value can be accessed via a zero-based index which is commonly expressed as a variable called i.
A zero-based index states that the first element of the array can be found by looking at index 0, not 1. You may come across programming challenges that try to trick your understanding of a zero-based index, versus a 1 based position – keep this in mind!
If we were to give the zero-based index i any given value:
- If
i = 0, thenarray[0]contains the value1. This is the first element in the array. - If
i =1, thenarray[1]contains the value1 - If
i = 5, thenarray[5]contains the value 0. This is the last element in the array.
We’ve just covered the first row of the problem sample!
A 2D (two-dimensional) array can be made by simply stacking multiple arrays on top of each other.
Therefore, we could define all of the first 2D array sample as:
var array1 = new int[] { 1, 1, 1, 0, 0, 0 };
var array2 = new int[] { 0, 1, 0, 0, 0, 0 };
var array3 = new int[] { 1, 1, 1, 0, 0, 0 };
var array4 = new int[] { 0, 0, 0, 0, 0, 0 };
var array5 = new int[] { 0, 0, 0, 0, 0, 0 };
var array6 = new int[] { 0, 0, 0, 0, 0, 0 };
This is not a 2D array, though. It simply lets us look at nicely formatted data that makes the shape of a 2D array (known as a matrix) in our text editor. Currently, we have just declared 6 integer array variables in isolation.
We can now create a 2D array by writing:
var twoDimensionalArray = new int[][] {array1, array2, array3, array4, array5, array6};
Our original arrays contained integers, and were defined as int[]. However, this new array does not contain integers. It contains integer arrays. int[][] is used to describe this – it is an integer array array (but its most easily spoken as array of integer arrays).
twoDimensionalArray[0] contains a reference to the integer array array1. This means that we can then perform a second lookup on array1 to find a specific integer value!
int[] array1Reference = twoDimensionalArray[0]; int integerValue = array1Reference[0]; // integerValue is 1
This two-part process can actually be simplified into a one-line command:
int integerValue = twoDimensionalArray[0][0]; // integerValue is 1
If we refer to the index of twoDimensionalArray an array as i, then we need another variable to refer to the index of an integer in the returned array. This is where j is introduced. These letters come from historical mathematical notation and are typically used in HackerRank programming questions.
As you will see in our solution, .Net allows us to name these variables whatever we like. It is strongly recommended that we do this, as it will dramatically increase the readability of our code!
How Should I Think About 2D Arrays?
Two-dimensional arrays form rows and columns. As we can see above, a 6 x 6 2D array has 6 rows and 6 columns of data, producing a matrix of 36 elements that can be retrieved with zero-based indices for row i and column j.
For example:
- If row
i = 0, and columnj = 0thentwoDimensionalArray[0][0]1. This is the top-left value in the 2D array, otherwise known as the first element ofarray1. - If row
i = 5, and columnj =5 thentwoDimensionalArray[5][5]0. This is the bottom-left value in the 2D array, otherwise known as the last element ofarray6.
Problems like this require iterating through the matrix of data. To achieve this, we loop through each row’s columns. This is called a nested loop.
twoDimensionalArray[0][0]twoDimensionalArray[0][1], then twoDimensionalArray[0][2]twoDimensionalArray[0][5]
At this point we have iterated through all of array1 and would then move to array2.
twoDimensionalArray[1][0]twoDimensionalArray[1][1], then twoDimensionalArray[1][2]twoDimensionalArray[1][5]
And so on. This can be generalised to the following pseudo-code.
for each row
for each column in the current row
do something
Key HackerRank Solution Concepts
The Hourglass
An Initial Brute Force Approach to Understand HackerRank Question Basics
Up until now, we have talked about iterating through a matrix element by element and covered the syntax for easily accessing elements. The hourglass in this question makes the problem appear more complex, however, because it expects us to look at seven elements at once!
We can see in the first example that they have drawn the shape of an hourglass with 1s in the example matrix:
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
We must imagine sliding the hourglass over this matrix into all 16 unique positions. How do we do this in .Net, though? Let’s start with calculating the first hourglass value.
In a brute-force approach, this first position could be hand-calculated as the sum of each part:
- Top of hourglass =
twoDimensionalArray[0][0]+twoDimensionalArray[0][1] +twoDimensionalArray[0][2] - Middle of hourglass =
twoDimensionalArray[1][1] - Bottom of hourglass =
twoDimensionalArray[2][0]+twoDimensionalArray[2][1] +twoDimensionalArray[2][2]
The second position could be hand-calculated as the sum of each part in the next position across:
- Top of hourglass =
twoDimensionalArray[0][1]+twoDimensionalArray[0][2] +twoDimensionalArray[0][3] - Middle of hourglass =
twoDimensionalArray[1][2] - Bottom of hourglass =
twoDimensionalArray[2][1]+twoDimensionalArray[2][2] +twoDimensionalArray[2][3]
This could be repeated until the top-right edge of the hourglass was on the last column of the first row. We’d need to repeat this 4 times for the first row.
This process would then repeat until the bottom-right of the hourglass was on the last column of the last row, producing 16 calculations. In this final position, the top of the hourglass would be in row 4 (or zero-based index 3).
Writing this out by hand would produce a functional solution. The calculation could be nicely functionally decomposed and reused for each calculation. However, it is not algorithmically minded.
While this problem says that the array will always be 6 x 6, it is typical that more advanced programming challenges will expect your solution to dynamically solve arrays of different sizes. Hand-coding function calls will not solve this as they focus on a specific array size.
Solving HackerRank Problems by Identifying Patterns from the Brute Force Approach
Did you notice that the top left of the hourglass followed our original matrix traversal approach? It started at the top left but, in this instance, only moved to the next column if the top right of the hourglass was within the bounds of the matrix. If the top right of the hourglass fell over the edge of the matrix in the next step across, it would start the next row and reset the column counter.
This is exactly the same logic as the original matrix traversal strategy; if we tried to move to the next column and there was no value there, it would drop to the next row and start at the first column.
Therefore:
- The top-left of the hourglass is always at the current row i column j index
- Every other element of the hourglass is relative to this position
- The top-middle element is 1 column to the right of the top-left, on the same row
- The top-right element is 2 columns to the right of the top-left, on the same row
- The middle element is 1 row below and 1 column to the right from the top-left
- Etc
We can write this new looping approach in pseudocode as:
for each row where the bottom of the hourglass does not extend beyond the matrix
for each column where the right side of the hourglass does not extend beyond the matrix
calculate the current hourglass' total, using indices relative to the top-left of the hourglass
The HackerRank .Net Hourglass Solution
class Result
{
/*
* Complete the 'hourglassSum' function below.
*
* The function is expected to return an INTEGER.
* The function accepts 2D_INTEGER_ARRAY arr as parameter.
*/
public static int hourglassSum(List<List<int>> arr)
{
int? highestValue = null;
for(int row = 0; row <= 3; row ++){
for (int column = 0; column <= 3; column++){
var column2 = column + 1;
var column3 = column + 2;
var row2 = row + 1;
var row3 = row + 2;
var currentValue =
arr[row][column] +
arr[row][column2] +
arr[row][column3] +
arr[row2][column2] +
arr[row3][column] +
arr[row3][column2] +
arr[row3][column3];
if (!highestValue.HasValue || currentValue > highestValue.Value){
highestValue = currentValue;
}
}
}
return highestValue.Value;
}
}
The HackerRank question asks for us to return the largest hourglass value. Therefore, we define an integer value to capture this. The question says that the value for any given integer in the 2D array can be in the range from -9 to 9, so this data type is large enough, as the biggest value that we can have is 7 hourglass elements * 9 = 63. HackerRank moderate and advanced questions often catch people out who do not pay attention to these details.
Now, we codify the pseudocode.
We have an outer loop that steps through each row. Because our matrix is a fixed size, we know that index 3 (row 4) is as far down as we can position the hourglass.
We have an inner loop that steps through each column. Because our matrix is a fixed size, we know that index 3 (column 4) is as far across as we can position the hourglass to the right.
“But Trent, hard coding the terminating loop conditions like that isn’t extensible! That’s bad code, you fail!!!”
Indeed, we can dynamically calculate the terminating conditions of the loops. The final column index - width of the hourglass for the inner loop, and the final row index - height of the hourglass for the outer loop. However, what value does this produce? These calculations introduce additional logic that increases the complexity of the solution. The question also explicitly specifies that the size of the matrix is fixed, meaning that they provide no functional benefit. While hard-coded values like this may not always be desirable, they are a great example of Sloth Code in action; code that’s a bit ugly, but very much appropriate for its current context.
To increase the readability of the solution, we calculate the index of the other rows and columns that form the hourglass. Without these, we’d have to repeat the index addition multiple times for each part of the hourglass, which could also be error-prone.
We then add each part of the hourglass together by looking up each array[i][j] and capture the result in a local variable that is scoped to the current nested loop calculation. This value is then compared to the highest value. If no highest value has been set (it is null), then we will set the current value as the highest. This will take place for our first hourglass calculation. Subsequently, each remaining hourglass will be compared to this value, and assigned if they are large than it.
Finally, we return the largest value.
Test out your solution in the HackerRank GUI. It will tell you whether you have catered to all of the HackerRank private test data or not.
Sloth Summary
This is a great programming challenge to practice abstract thinking. You need to be able to visualise an hourglass sliding over a data matrix to understand the core ask of the question. This is not something one practices daily!
From this abstract concept, you need to understand the .Net data structure(s) that can model the data and how to access the data from them.
At times, it can be helpful to brute-force solve one or two of the many scenarios that a question demands. This may make it easier to identify algorithmic patterns that will help you convert a hand-coded (hard-coded) solution into a more dynamic and considered algorithm to solve the problem.
Finally, HackerRank challenges are fun; however, it is highly unlikely that you will be able to solve these types of problems without first discovering and learning about them. Now that you understand this challenge’s concepts, you can leverage this experience to solve similar problems. The more problems you discover, the easier subsequent challenges are to solve!
Happy Code Slothing!
