Question:
We define an hourglass in to be a subset of values with indices falling in this pattern in 's graphical representation:
a b c
d
e f g
There are hourglasses in , and an hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in , then print the maximum hourglass sum.
For example, given the 2D array:
-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
We calculate the following hourglass values:
-63, -34, -9, 12,
-10, 0, 28, 23,
-27, -11, -2, 10,
9, 17, 25, 18
Our highest hourglass value is from the hourglass:
0 4 3
1
8 6 6
Solution:
The Solution is simple you just have to calculate the sum of the window or the hour glass and you would have to keep track of the previous maximum sum.
For better understanding, here is the code.
int maxSum=-100;
int r=0,s=0,p=0,q=0,sum=0,m=0,i=0,j=0,row=0,col=0,k=0;
for(row=0;row<arr[0].length-2;row++){
for(col=0;col<arr.length-2;col++)
{
i=arr[row][col];
j=arr[row][col+1];
k=arr[row][col+2];
m=arr[row+1][col+1];
p=arr[row+2][col];
q=arr[row+2][col+1];
r=arr[row+2][col+2];
sum=p+q+r+i+j+k+m;
if(sum>maxSum){
maxSum=sum;
}
}
}
System.out.print(maxSum);
return maxSum;
}
static int hourglassSum(int[][] arr) {
int maxSum=-100;
int r=0,s=0,p=0,q=0,sum=0,m=0,i=0,j=0,row=0,col=0,k=0;
for(row=0;row<arr[0].length-2;row++){
for(col=0;col<arr.length-2;col++)
{
i=arr[row][col];
j=arr[row][col+1];
k=arr[row][col+2];
m=arr[row+1][col+1];
p=arr[row+2][col];
q=arr[row+2][col+1];
r=arr[row+2][col+2];
sum=p+q+r+i+j+k+m;
if(sum>maxSum){
maxSum=sum;
}
}
}
System.out.print(maxSum);
return maxSum;
}
Hackerrank Java Solution: 2D Array - DS
Reviewed by Jas Arora
on
May 29, 2020
Rating:
No comments:
If you have any doubts please let me know.