# Solution of “Extended” Hourglass Sum problem of Hackerrank in C#

Problem source: Compute Hourglass Sum of a 2D array.

Note: Original problem is having 6 rows and 6 columns. But in this solution I’ve extended it little bit so that it can be used for n x n (n>= 3).

Given a 6×6 2D Array, :

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 define an hourglass in A to be a subset of values with indices falling in this pattern in A‘s graphical representation:

a b c
d
e f g

There are 16 hourglasses in A, and an hourglass sum is the sum of an hourglass’ values.

Calculate the hourglass sum for every hourglass in A, then print the maximum hourglass sum.

Input Format

There are 2 or more lines of input, where each line contains 3 or more space-separated integers describing 2D Array A; every value in A will be in the inclusive range of -9 to 9.

Constraints

-9 <= A[i][j]<=9

0 <= i,j<= 5

Output Format

Print the largest (maximum) hourglass sum found in A.

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

A contains the following hourglasses:

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

The hourglass with the maximum sum (19) is:

2 4 4
2
1 2 4

Code in C#

class HourglassSum
{
static void Main(string[] args)
{
int[][] arr = new int[6][];
for (int arr_i = 0; arr_i < 6; arr_i++)
{
arr[arr_i] = Array.ConvertAll(arr_temp, Int32.Parse);
}

Console.WriteLine(CalculateHourGlassSum(arr));
}

private static int CalculateHourGlassSum(int[][] arr)
{
/* Whatever the count of the rows of the array,
our loop should run till n -2. For example
row count is 3, in this case loop should run only once
123
546
156

Because this is a perfect hourglass, so sum of this is
our answer. So our loop should run just 1 time.
45689
41256
02530
00000
in this case total rows are 4, and there can be at max
3 hourglass, so 5 - 2 = 3, so we need to run the loop
only 3 times.
*/
int rowCount = arr.Length - 2;
int maxSum = int.MinValue;
for (int i = 0; i < rowCount; i++)
{
/// Same logic that we are using for rows will be
/// applicable for columns too.
int columnCount = arr[i].Length - 2;
for (int j = 0; j < columnCount; j++)
{
/*
for example our array is as below:
Rows: i = 0, Columns: j = 0
45612
07000
45872
33333
66666

to compute sum of hourglass we have below formula:
Sum = arr[i][j]        = 4
+ arr[i][j + 1]        = 5
+ arr[i][j + 2]        = 6
+ arr[i + 1][j + 1]    = 7
+ arr[i + 2][j]        = 4
+ arr[i + 2][j + 1]    = 5
+ arr[i + 2][j + 2]    = 8
*/
int 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];
if (maxSum < sum)
{
maxSum = sum;
}
}
}
return maxSum;
}
}

## 2 thoughts on “Solution of “Extended” Hourglass Sum problem of Hackerrank in C#”

1. Ankit Bajpai says:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HackerRankPractice
{
class Class1
{
static int[][] CreateHourGlassForIndexAndSumIt(int p, int q, int[][] arr)
{
int[][] hourGlass = new int[3][];

int x = 0, y = 0;
for (int i = p; i <= p + 2; i++)
{
hourGlass[x] = new int[3];
int[] temp = new int[3];
int k = 0;
for (int j = q; j <= q + 2; j++)
{
temp[k] = arr[i][j];
k++;
}
hourGlass[x] = temp;
x++;
}

return hourGlass;
}

static int findSumOfEachHourGlass(int[][] arr)
{
int sum = 0;
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr.Length; j++)
{
if (!((i == 1 && j == 0) || (i == 1 && j == 2)))
sum += arr[i][j];
}

}

return sum;
}

static void Main(string[] args)
{
int[][] arr = new int[6][];
for (int arr_i = 0; arr_i < 6; arr_i++)
{
arr[arr_i] = Array.ConvertAll(arr_temp, Int32.Parse);
}

int[] sum = new int[16];
int k = 0;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
int[][] hourGlass = CreateHourGlassForIndexAndSumIt(i, j, arr);
sum[k] = findSumOfEachHourGlass(hourGlass);
k++;
}
}

Console.WriteLine(sum.Max());

}
}
}

Like

2. Ankit Bajpai says:

class Class1
{
static int[][] CreateHourGlassForIndexAndSumIt(int p, int q, int[][] arr)
{
int[][] hourGlass = new int[3][];

int x = 0, y = 0;
for (int i = p; i <= p + 2; i++)
{
hourGlass[x] = new int[3];
int[] temp = new int[3];
int k = 0;
for (int j = q; j <= q + 2; j++)
{
temp[k] = arr[i][j];
k++;
}
hourGlass[x] = temp;
x++;
}

return hourGlass;
}

static int findSumOfEachHourGlass(int[][] arr)
{
int sum = 0;
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr.Length; j++)
{
if (!((i == 1 && j == 0) || (i == 1 && j == 2)))
sum += arr[i][j];
}

}

return sum;
}

static void Main(string[] args)
{
int[][] arr = new int[6][];
for (int arr_i = 0; arr_i < 6; arr_i++)
{
arr[arr_i] = Array.ConvertAll(arr_temp, Int32.Parse);
}

int[] sum = new int[16];
int k = 0;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
int[][] hourGlass = CreateHourGlassForIndexAndSumIt(i, j, arr);
sum[k] = findSumOfEachHourGlass(hourGlass);
k++;
}
}
//max in sum array
Console.WriteLine(sum.Max());

}
}

Like