HackerRank 2D Arrays - DS problem solution

In this HackerRank 2D Arrays - DS problem, we need to develop a program that can take a 2-dimensional integer array as input and then calculate the sum of every hourglass that present in that array.

what is an hourglass in an array?

let's say we have a 2-dimensional array. just like as shown below.

a  b  c  0  0  0

0  d  0  0  0  0

e  f   g  0  0  0

0  0  0  0  0  0

0  0  0  0  0  0

0  0  0  0  0  0

so here the one hourglass of an array is that follows the pattern. just like this...

a b c

  d  

e f g

so if we have an array of size 6x6 then there is 16 hourglass present in the array. so here in this problem, we need to print the hourglass sum that has a maximum value. and the input array is fixed that is a 6x6 or 2-dimensional array.

Problem solution in 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)

Explanation

Here we first define two variable n = 6 and m that has an empty list/array. after that, we take the input using for loop and store the input in the array m using the map function. after that, we find the sum of the hourglass using the sum_glass function. you can see the logic behind it. after that in the best variable we storing the - infinity value and then using for loop for every iteration of the array we are calling the sum_glass function and after that, we are comparing with the best variable to find the maximum value of the hourglass.

Problem solution in 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;
		
	}

}

Explanation

Here in the above code, the logic is that we use a total variable that has an initial value of 0. after that to find the value of an hourglass in the array we are finding the values one row at a time. as you could see in the above code in the last for loop we are finding the value of the first row and then the second and then the third row. and adding it to the total variable and then comparing with the max variable to find the max value of hourglass in the array. 

remember that in the above code in the first line of last for loop we are not adding it to the total variable instead, we are just initializing the value to the total variable. so we don't need to follow an extra step to make the value 0 of the total variable every time in the iteration of for loop.

Problem solution in 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;
}

Explanation

Here in the above code logic is pretty simple we make a sum function and also we are using a fixed size of an array in the program. and in the sum function, we are returning the sum of every hourglass that present in the array and addition all the values in just one line of code. the logic is the same as we did in the python program.

Problem solution in 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;
}

Explanation

Here in the above c program, we are using the fixed length of the array. and then using for loop we are scanning the input values and store them in the array. after that, we are using the for loop to find the sum of each hourglass that present in the array. remember here we are following the one additional step in the for a loop. and to optimize it you can also remove the sum = 0 and use the sum = a[i][j].