Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Given a 6 * 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 arrs 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 , then print the maximum hourglass sum. The array will always be 6 * 6.
Example
arr =
-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 16 hourglass sums are:
-63, -34, -9, 12,
-10, 0, 28, 23,
-27, -11, -2, 10,
9, 17, 25, 18
The highest hourglass sum is 28 from the hourglass beginning at row 1 , column 2:
0 4 3
1
8 6 6
Note: If you have already solved the Java domain's Java 2D Array challenge, you may wish to skip this challenge.
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,j <= 5
Output Format
Print the largest (maximum) hourglass sum found in arr.
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
arr ontains the following hourglasses:
The hourglass with the maximum sum (19) is:2 4 4
2
1 2 4
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int a[6][6];
int i, j;
for (i=0; i < 6; i++){
for (j=0; j < 6; j++) {
scanf("%d", &a[i][j]);
}
}
int out=-100, sum=0;
for (i=0; i < 4; i++){
for (j=0; j < 4; j++) {
sum = 0;
sum += a[i][j];
sum += a[i][j+1];
sum += a[i][j+2];
sum += a[i+1][j+1];
sum += a[i+2][j];
sum += a[i+2][j+1];
sum += a[i+2][j+2];
if (sum > out){
out = sum;
}
}
}
printf("%d", out);
return 0;
}
Copy The Code &
Try With Live Editor
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int arr[7][7];
int sum(int stx , int sty){
return arr[stx][sty] + arr[stx][sty+1] + arr[stx][sty+2] + arr[stx+1][sty+1] + arr[stx+2][sty] + arr[stx+2][sty+1] + arr[stx+2][sty+2];
}
int main() {
int ans = -100;
for(int i = 0 ; i < 6 ; i++){
for(int j = 0 ; j < 6 ; j++){
cin >> arr[i][j];
}
}
for(int i = 0 ; i < 4 ; i++){
for(int j = 0 ; j < 4 ; j++){
ans = max(ans , sum(i,j));
}
}
cout << ans << endl;
return 0;
}
Copy The Code &
Try With Live Editor
#4 Code Example with Java Programming
Code -
Java Programming
import java.util.Scanner;
public class Intro2dArray {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int multiDimArr[][] = new int[6][6];
for(int row = 0; row < 6; row++){
for(int col = 0; col < 6; col++){
multiDimArr[row][col] = sc.nextInt();
}
}
System.out.println(Solve(multiDimArr));
}
static int Solve(int arr[][]){
int max = Integer.MIN_VALUE;
int total = 0;
for(int row = 0; row < 4; row++){
for(int col = 0; col < 4; col++ ){
total = arr[row][col] + arr[row][col + 1] + arr[row][col + 2];
total += arr[row+1][col+1];
total += arr[row + 2][col] + arr[row+2][col + 1] + arr[row+2][col + 2];
max = total>max?total:max;
}
}
return max;
}
}
Copy The Code &
Try With Live Editor
#5 Code Example with Javascript Programming
Code -
Javascript Programming
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'hourglassSum' function below.
*
* The function is expected to return an INTEGER.
* The function accepts 2D_INTEGER_ARRAY arr as parameter.
*/
function hourglassSum(arr) {
// Write your code here
let maxSum = ''
for (let step1 = 0; step1 < arr.length-2; step1++){
for (let step2 = 0; step2 < arr.length-2; step2++){
const currentSum = arr[step1][step2] + arr[step1][step2+1]
+ arr[step1][step2+2] + arr[step1+1][step2+1]
+ arr[step1+2][step2] + arr[step1+2][step2+1]
+ arr[step1+2][step2+2]
if(currentSum <= 0){
const temp = currentSum
if (typeof maxSum == 'string' ){
maxSum = temp
} else if(temp == 0 && maxSum < = 0>{
maxSum = temp
}
else if(temp > maxSum){
maxSum = temp
}
} else if(currentSum > maxSum){
maxSum = currentSum
}
}
}
return maxSum
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
let arr = Array(6);
for (let i = 0; i < 6; i++) {
arr[i] = readLine().replace(/\s+$/g, '').split(' '>.map(arrTemp => parseInt(arrTemp, 10));
}
const result = hourglassSum(arr);
ws.write(result + '\n');
ws.end();
}
Copy The Code &
Try With Live Editor
#6 Code Example with Python Programming
Code -
Python Programming
n = 6
m = []
for i in range(n):
m.append(list(map(int, input().split()[:n])))
def sum_glass(m, i, j):
"""Assumes hour-glass is in bounds of m!"""
return sum(m[i][j:j + 3]) + m[i + 1][j + 1] + sum(m[i + 2][j:j + 3])
best = float("-inf")
for i in range(4):
for j in range(4):
s = sum_glass(m, i, j)
if s > best:
best = s
print (best)
Copy The Code &
Try With Live Editor