Finding the Sum of Hourglasses in a Matrix …but Make it Efficient
I’ve been working through HackerRank’s 30 Days of Coding tutorial to refresh my base skill set and find any knowledge gaps. Today, I worked on the problem for Day 11: 2D Arrays. The final solution for this problem where I have allowed for different sized matrices and added error handling for if a user inputs a value with mismatched rows and columns can be found my GitHub repo. Most solutions I’ve seen for this problem come out to O(n^2) efficiency at best, but I have created a solution yielding O(n).
The basic concept of the problem is to find the sum of hourglasses in a 6x6 matrix represented by a 2-Dimension Array like so:
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
For the problem, an hourglass is represented by this graphical pattern:
A B C
D
E F G
In the example array, the first hourglass is
1 1 1
0 1 0
1 1 1
and the second hourglass would be
1 1 0
0
1 1 0
The goal of the problem is to 1) find all of the hourglasses in a square matrix, 2) find the sum of all of the digits in each hourglass, and 3) return the largest sum found.
Approach 1 - Brute Force
The initial approach I took was to loop through each row and then use each column in the row to find the first hourglass associated with it. This approach worked and passed all of HackerRank’s tests.
class Solution
{
//extract the hourglasses
public static List<List<int>> getHourglasses(List<List<int>> pattern)
{
int width = 3;
int height = 3;
List<int> hourglass = new List<int>();
List<List<int>> hourglasses = new List<List<int>>();
for(int i = 0; i<pattern.Count - 2; i++)
{
for(int j = 0; j<pattern[i].Count - 2;j++)
{
hourglass = new List<int>();
//extract top
hourglass.AddRange(pattern[i].GetRange(j, width));
//extract middle
hourglass.Add(pattern[i+1][j+1]);
//extract bottom
hourglass.AddRange(pattern[i+2].GetRange(j, width));
hourglasses.Add(hourglass);
}
}
return hourglasses;
}
public static void Main(string[] args)
{
List<List<int>> arr = new List<List<int>>();
for (int i = 0; i < 6; i++)
{
arr.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(arrTemp => Convert.ToInt32(arrTemp)).ToList());
}
//if the answer is < 0, max = 0 messes it up
//-63 is the smallest answer
int max = -99;
var hourglasses = getHourglasses(arr);
foreach(var hourglass in hourglasses)
{
int result = hourglass.Sum();
if(result > max)
max = result;
}
Console.WriteLine(max);
}
}Approach 2 - O(n)
Though this approach works well for the limits of the coding problem, I wanted to make it more usable to a real life scenario. The Big O Notation for this code as is would actually only be O(1) because in the confines of the HackerRank challenge, “pattern.Count” will always be 6. But what if we wanted this to take in a matrix of any size? The efficiency quickly rises to O(N^2) at best due to the nested for loop. I wanted to find a way to make this better.
The first change I made was to remove the foreach loop in the Main function. This might not change the overall efficiency, but it still improves our overall speed. I moved the sum calculation into the getHourglasses function.
Original
//if the answer is < 0, max = 0 messes it up
//-63 is the smallest answer
int max = -99;
var hourglasses = getHourglasses(arr);
foreach(var hourglass in hourglasses)
{
int result = hourglass.Sum();
if(result > max)
max = result;
}
Console.WriteLine(max);New Approach
var answer = getMaxHourglassSum(arr);
if(answer == null)
Console.WriteLine("Please submit a square matrix.");
else
Console.WriteLine(getMaxHourglassSum(arr));
Original
for(int i = 0; i<pattern.Count - 2; i++)
{
for(int j = 0; j<pattern[i].Count - 2;j++)
{
hourglass = new List<int>();
//extract top
hourglass.AddRange(pattern[i].GetRange(j, width));
//extract middle
hourglass.Add(pattern[i+1][j+1]);
//extract bottom
hourglass.AddRange(pattern[i+2].GetRange(j, width));
hourglasses.Add(hourglass);
}
}
return hourglasses;New Approach
for(int i = 0; i<pattern.Count - 2; i++)
{
for(int j = 0; j<pattern[i].Count - 2;j++)
{
hourglass = new List<int>();
//extract top
hourglass.AddRange(pattern[i].GetRange(j, width));
//extract middle
hourglass.Add(pattern[i+1][j+1]);
//extract bottom
hourglass.AddRange(pattern[i+2].GetRange(j, width));
//find sum
int sum = hourglass.Sum();
//check if sum is the max
if(sum > max)
{
max = sum;
}
}
return max;The next task was to find a way to traverse the matrix without using a nested for loop. To do so, I settled on computing the starting coordinates for matrix through C#’s arithmetic operation rules.
Division (/)
In C# (and many other programming languages) for integers, division deals only in whole numbers. 10 / 5 = 2 and 11 / 5 = 2.
Remainder (%)
The % operator in C# (and many other languages) returns the remainder of division calculated by a - (a / b) * b. 10 % 5 = 0 because 5 divides 10 evenly. 11 % 5 = 1 because there is a remainder of 11/5. This also means that 3 % 5 = 3 because 3 - (3/5) = 3 - 0 = 3.
Keeping these rules in mind, I used them with the total number spaces in the matrix to find coordinates. For example, let’s look at the following:
If we a 6x6 matrix like so, it has 36 total slots (indexes).
1 1 1 0 0 0 -> 0 1 2 3 4 5
0 1 0 0 0 0 -> 6 7 8 9 10 11
1 1 1 0 0 0 -> 12 13 14 15 16 17
0 0 0 0 0 0 -> 18 19 20 21 22 23
0 0 0 0 0 0 -> 24 25 26 27 28 29
0 0 0 0 0 0 -> 30 31 32 33 34 35
On a coordinates graph, it can be denoted as
(0,0) (0,1) (0,2) (0,3) (0,4) (0,5)
(1,0) (1,1) (1,2) (1,3) (1,4) (1,5)
(2,0) (2,1) (2,2) (2,3) (2,4) (2,5)
(3,0) (3,1) (3,2) (3,3) (3,4) (3,5)
(4,0) (4,1) (4,2) (4,3) (4,4) (4,5)
(4,0) (4,1) (4,2) (4,3) (4,4) (4,5)
By dividing each index by the number of rows (or columns since a matrix is a square) and taking the remainder of each index divided by the number of rows, we can find the the coordinates given above.
index = 0, numberOfRows = 6
0/6 = 0
0%6 = 0
(0,0)
index = 1, numberOfRows = 6
1/6 = 0
1%6 = 1
(0,1)
index = 27, numberOfRows = 6
27/6 = 4
27%6 = 3
(4,3)
Using this approach, I implemented the following change to my function:
After
Before
for(int i = 0; i<pattern.Count - 2; i++)
{
for(int j = 0; j<pattern[i].Count - 2;j++)
{
hourglass = new List<int>();
//extract top
hourglass.AddRange(pattern[i].GetRange(j, width));
//extract middle
hourglass.Add(pattern[i+1][j+1]);
//extract bottom
hourglass.AddRange(pattern[i+2].GetRange(j, width));
//find sum
int sum = hourglass.Sum();
//check if sum is the max
if(sum > max)
{
max = sum;
}
}for(int i = 0; i < (matrixwidth-(width-1)) * (matrixheight-(width-1)) ; i++)
{
// Find row and column index
int row = i / (matrixheight-(width-1)) ;
int col = i % (matrixwidth-(width-1)) ;
//make a new hourglass
hourglass = new List<int>();
//extract top
hourglass.AddRange(pattern[row].GetRange(col, width));
//extract middle
hourglass.Add(pattern[row+1][col+1]);
//extract bottom
hourglass.AddRange(pattern[row+2].GetRange(col, width));
//find sum
int sum = hourglass.Sum();
//check if sum is the max
if(sum > max)
{
max = sum;
}
}After adding the changes, the Big(O) notation for my solution is reduced to O(n) from O(n^2). This also allows users to input a matrix of any size instead of being limited to just six rows. The code could be further improved by reading the input in by stream instead of hardcoding the number of rows (line 70 in the repo). The completed source code can be found on my GitHub repo.
