# Day 11: 2D Arrays

# Day 11: 2D Arrays

abhi007tyagi + 66 comments my solution

`int sum[] = new int[16]; int h = 0; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { sum[h] = 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]; h++; } } Arrays.sort(sum); System.out.println(sum[15]);`

NemesisRex + 17 comments This one is good! How would the solution look if we were given a n x n matrix, rather than a strict 6 x 6 matrix?

rajasekhariiith + 1 comment I guess as long as we know the given matrix is a square matrix, hour glass size and n we can implement this solution. Anything beyond that beats the purpose of tutorials.

NemesisRex + 2 comments Yes I know. I am just speculating that it would be nice with a solution for aribtrary hour glass size and n values given that the matrix is square.

rajasekhariiith + 1 comment Yes, it would be nice in Arrays, Algorithm section.

abcoder4 + 1 comment `#define SIZE 6 #define SIZE_GLASS 3 int main(void){ vector< vector<int> > arr(SIZE,vector<int>(SIZE)); for(int arr_i = 0; arr_i < SIZE; arr_i++){ for(int arr_j = 0; arr_j < SIZE; arr_j++){ cin >> arr[arr_i][arr_j]; } } int max = INT_MIN; for(int arr_i = 0; arr_i<SIZE-SIZE_GLASS+1; arr_i++){ for(int arr_j=0; arr_j<SIZE-SIZE_GLASS+1; arr_j++){ int sum = 0; for(int x=arr_j; x<arr_j+SIZE_GLASS; x++) sum += arr[arr_i][x]; for(int x=arr_j; x<arr_j+SIZE_GLASS; x++) sum += arr[arr_i+SIZE_GLASS-1][x]; sum += arr[arr_i+1][arr_j+1]; if(sum>max){ max = sum; } } } cout << max; return 0; }`

// This will work for different sized arrays but not different sized matrices since I also need to add in the loop for lower n upper triangle

// There r negative sums too in the hourglass' max sum too so it works fine with INT_MIN

neerajnitjsr20 + 1 comment # include

# include

# include

# include

# include

# include

# include

int main(){ int arr[6][6],k,max=0,temp,sum[5],sum1[5],sum2[5],arr_i,arr_j; for(arr_i = 0; arr_i < 6; arr_i++){ for( arr_j = 0; arr_j < 6; arr_j++){

`scanf("%d",&arr[arr_i][arr_j]); } } for(arr_i=0;arr_i<4;arr_i++) { for(arr_j=0;arr_j<=4;arr_j++) { sum[arr_j]=arr[arr_i][arr_j]+arr[arr_i][arr_j+1]+arr[arr_i][arr_j+2]; } for(arr_j=0;arr_j<=4;arr_j++){ sum1[arr_j]=arr[arr_i+1][arr_j+1]; // printf("...%d %d..\n",j, sum1[i]); } for(arr_j=0;arr_j<=4;arr_j++) sum2[arr_j]=arr[arr_i+2][arr_j]+arr[arr_i+2][arr_j+1]+arr[arr_i+2][arr_j+2]; for(k=0;k<5;k++) { temp=sum[k]+sum1[k]+sum2[k]; if(max<temp) { max=temp; } else temp=temp; } } printf("%d",max); return 0;`

}

neerajnitjsr20 + 0 comments In code block this code is running but not here

gandivenkatesh11 + 1 comment In that case instesd of using 4 we can use n-2 in loop

rajsinha1a + 0 comments we can adjust the value according to hour glass given. If hourglass is of 3X3 then n-2 otherwise n-1-hourglass value. both matrices need to be square matrix.

moonimbu + 0 comments at that time instead of for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) {

use - for (int i = 0; i < n-2; i++) { for (int j = 0; j < n-2; j++) {

sourav_raychaud1 + 0 comments [deleted]HAAdams + 0 comments `Through a simple calculation, from an NxN matrix, there are (N-2)*(N-2) hourglasses. Hence, alll you have to do is to find N-2 and replece the i<4 and j<4 to i<N-2 and j<N-2 respectively.`

alex92 + 0 comments [deleted]ppdusa + 0 comments Hello, NemesisRex. If that is n x x matrix then both loops should be till n-2. Like here we have (6-2) = 4. Hope this will help.

itshimalaykumarx + 0 comments set the size of sum array to (N-2)*(N-2) provided tha given array is square and row and column are in multiple of 3.

dimio + 0 comments Maybe so (matrix of any size, but not less than the size of the hourglass):

#!/usr/bin/perl use warnings; use strict; use utf8; #hourglass dimensions, min 3x3 my $hg_dim = { 'x' => 5, #width, must be odd 'y' => 4, #height }; $hg_dim->{wdht} = $hg_dim->{x}-1; #i $hg_dim->{hght} = $hg_dim->{y}-1; #j $hg_dim->{cntr} = sprintf("%u", $hg_dim->{x}/2); my $arr = []; while(<STDIN>){ chomp; push $arr, [split(' ', $_)]; } # ...or $#{$arr-$hg_dim-1>[0]}+1 - $hg_dim-1 my $max_x = (scalar @{$arr->[0]}) - ($hg_dim->{wdht}); my $max_y = (scalar @{$arr}) - ($hg_dim->{hght}); # for neg nums, or add $sum on array and sort it my $max_sum = -1000; for (my $y = 0; $y < $max_y; $y++){ for (my $x = 0; $x < $max_x; $x++){ my $sum = 0; for (my $i = $x; $i <= $x+$hg_dim->{wdht}; $i++){ $sum += $arr->[$y]->[$i]; #upper row $sum += $arr->[$y+$hg_dim->{hght}]->[$i]; #lowest row } for (my $j = $y+1; $j < $y+$hg_dim->{hght}; $j++){ $sum += $arr->[$j]->[$x+$hg_dim->{cntr}]; #column } $max_sum = ($sum > $max_sum) ? $sum : $max_sum; } } print $max_sum, $/;

It's complete all Test Cases and I tested it on this matrix (7x8):

1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 7 4 4 0 3 0 0 0 2 0 0 5 4 4 4 2 4 0 0 1 6 3 4 0 8 2 4 4 4 0 0 0 1

mail2chetan + 0 comments //scala object Solution { var maxArray = Array.ofDim[Int](3, 3) var maxSum = -50

`// To print Array if you want`

def printmaxArray{ val i = 3; val j = 3 for(i <- 0 to i-1) { for(j <- 0 to j-1){ if( (i!=1 || j!=0) && (i!=1 || j!=2)) { print(maxArray(i)(j)+" ") } else print(" ") } println } }

`def hrsum(array: Array[Array[Int]]) = { if (array.length == 3) { var total = 0 val len = array.length - 1 for (row <- 0 to len) for (col <- 0 to len) { total += array(row)(col) } total -= (array(1)(0) + array(1)(2)) if (total > Solution.maxSum) { Solution.maxSum = total Solution.maxArray = array // printmaxArray } }`

}

`def hourglassindex(arr: Array[Array[Int]]) = { var totalsum = 0 var hrlist: List[Int] = List() var tempArr = Array.ofDim[Int](3, 3); val i = 3; val j = 3 var row = 0; var col = 0 var num = 0; for (row <- 0 to 3) { for (col <- 0 to 3) { var temprow = 0; var tempcol = 0; for (movingrow <- row to (row + 2)) { for (movingcol <- col to (col + 2)) { tempArr(temprow)(tempcol) = arr(movingrow)(movingcol) tempcol += 1 } temprow += 1 tempcol = 0 } hrsum(tempArr) num += 1 } }`

}

`def main(args: Array[String]) { val sc = new java.util.Scanner (System.in); val n = 6 // n x n matrix var arr = Array.ofDim[Int](n,n); for(arr_i <- 0 to n-1) { for(arr_j <- 0 to n-1){ arr(arr_i)(arr_j) = sc.nextInt(); } } hourglassindex(arr) println(maxSum) }`

}

guptapakhi08 + 2 comments int s=0,max=0;

`for(int i=0; i<(n-2); i++) { for(int j=0;j<(n-2);j++) { s = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2]+a[i+1][j+1]; if(max<s) max=s; } } System.out.println(max); if you want to change the size of the hourglass too, then use loops for calculating s.`

ashwinphilip27 + 1 comment What is n?

guptapakhi08 + 0 comments It is the size of the array.

sanjeet_skg + 3 comments if you take max=0, then test case 3 and 8 will fail.

abhijit25k + 1 comment same is happening for me as well... How to work around that?

sanjeet_skg + 2 comments As the value range starts from -9 and the total hours glass has 7 elements so I have taken int maxSum = -63; In general you can take int maxSum = Integer.MIN_VALUE.

abhijit25k + 0 comments Thanks for explaining... Because of -ve elements taking zero will fail for two testcases... Now got it..

suryodaya_s44 + 0 comments take max as int max = arr[0][0] + arr[0][1] + arr[0][2] + arr[1][1] + arr[2][0] + arr[2][1] + arr[2][2];

kartiksrivastav4 + 0 comments thanks bhai was stuck thinking every thing is alright then saw this changed the max =-1000 and worked as everything was working perfectly.

prakharshukla201 + 0 comments if there is a square matrix of size n then all we can do is to traverse half way in it but first we will see if N is odd or even and n should be more than 3 (for hour glass formation). like if its 6 then traverse the i th and j th elements by running a loop till 3. if n= odd number ,like 9 then (n+1)/2= 5 traverse the i th and j th elements by running a loop till 5.

anjuviswan + 0 comments [deleted]anshuman854 + 1 comment import java.io.

*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*;public class Solution {

`private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int[][] arr = new int[6][6]; for (int i = 0; i < 6; i++) { String[] arrRowItems = scanner.nextLine().split(" "); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int j = 0; j < 6; j++) { int arrItem = Integer.parseInt(arrRowItems[j]); arr[i][j] = arrItem; } } scanner.close(); int max=-63; int sum=0; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ 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(sum>max){ max=sum; } sum=0; } } System.out.println(max); }`

}

cankush625 + 1 comment It works! Good solution and understandable

monisms15 + 0 comments I have done the following with the complexity of O(n).. Hope, it will help one of those who are here just to have some more optimized code..All thanks to the AlMighty, who have given me the power to do this ,#Allhamdulillah. public static void SumHourGlass(int [][] hourGlass) { int maximum = 0; int a = 0, b = 1, c = 2; int d = 1; int e = 0, f = 1, g = 2; int row1 = 0; int row2 = 1; int row3 = 2; for (int i = 1; i <= 16; i++) { int sum = hourGlass[row1][a] + hourGlass[row1][b] + hourGlass[row1][c] + hourGlass[row2][d] + hourGlass[row3][e] + hourGlass[row3][f] + hourGlass[row3][g];

`if (i == 1) { maximum = sum; } if (i > 1) { if (sum > maximum) { maximum = sum; } } if (i % 4 != 0) { a++; b++; c++; d++; e++; f++; g++; } else { a = 0; b = 1; c = 2; d = 1; e = 0; f = 1; g = 2; row1++; row2++; row3++; } } Console.WriteLine(maximum); }`

raju_muke + 0 comments I think you ar elooking for this solution

int max = Integer.MIN_VALUE,sum=0;

for(int i=0;i<4;i++){

for(int j=0;j<4;j++){

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(sum>max){ max=sum; }

} }System.out.println(max);

akashanil14 + 0 comments `then the i and j loop will run till i,j < n-2`

amiteshrajvaidy1 + 0 comments for nxn matrix the loops for both row and column will go upto n-2

kasusaland + 0 comments that is more complex .. but is this circumstances this is just fine

teckvui78 + 0 comments [deleted]maximshen + 3 comments 1) You don't need to increase time complexity by sorting the array afterwards, you should get the ongoing max value.

2) You don't need to increase space complexity by creating a int array.robertwilk + 1 comment That's a valid point since it will take more time but there isn't an

*increase*to the time complexity; is there? To determine all the sums takes*O(n^2)*; yes? Adding*n log n*to that would be dropped as insignificant.Thiez + 2 comments Determining all sums is in O(n).

robertwilk + 0 comments I'd appreciate if you could explain that. I don't see how you can find the various sums of an nxn matrix in

*O(n)*time. Finding a sum of a particular hourglass would be a constant factor but you do that*(n-2)(n-2) = n^2-4n+4 = O(n^2)*times as you iterate over both dimensions of the array.robertwilk + 1 comment I'm going to preempt any response you plan to give since your claim bugs me.

This problem is a slight variation of the summing all sub-matrices of size

*m x m*in an*n x n*matrix. The variations are 1) the sub-matrix (hourglass) has a fixed size (*3 x 3*) and 2) we don't sum the entire matrix since it's an hourglass. That's the only reason the summing part is a constant factor.If we altered this problem to say

*n*is always even and the hourglass is always*n/2*the complexity would then be*O(n^4)*because the innermost loop would be a function of*n*. So, we'd end up with:*(n - (n/2 - 1))^2(n/2)^2 = O(n^4)*In fact, if we take this problem back to the one it's a variation of, drop the hourglass constraints, and allow for any sub-matrix of size

*m x m*in an*n x n*matrix such that*n > m*the non-dynamic solution has a complexity of*O(n^2m^2)*. Because we'd then have:*(n - (m - 1))^2m^2 = O(n^2m^2)*That's my line of thought about the complexity. The only way I see

*O(n)*being reasonable is if you consider*n*to be fixed and the*(n - 2)^2*part to be a coefficient on*n*but, aside from that being uninteresting analysis, that neglects the fact the coefficient is actually a function of*n*with greater significance.If you like, please respond with the math you came up with to get

*O(n)*complexity.Thiez + 0 comments I assumed fixed-size hourglasses, and my

`n`

is the number of entries in the matrix, not the dimensions of the matrix.

dseelin + 9 comments Yup! This is what I used.

int max_sum = 0; int temp_sum; for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { temp_sum = 0; // top row temp_sum += arr[i][j]; temp_sum += arr[i][j+1]; temp_sum += arr[i][j+2]; //middle temp_sum += arr[i+1][j+1]; //bottom row temp_sum += arr[i+2][j]; temp_sum += arr[i+2][j+1]; temp_sum += arr[i+2][j+2]; //if first hourglass, set as max if(temp_sum > max_sum || i == 0 && j == 0) max_sum = temp_sum; } } cout << max_sum;

hacknik246 + 0 comments Most clear solution Ive seen. Cheers

a_shivani63 + 2 comments could you please explain me why you have taken the condition i==0 && j==0 in if condition?

priyankaagrawal2 + 0 comments i Guess it is just to set the max_sum with the value of first hourglass. So that doesn't need to handle negative value separately i-e no need to initialse max_value with minimum Integer(Integer.MIN_VALUE);

lokesh_30996 + 0 comments For the first time i.e., at i==0 and j==0, there is no value for max_sum but we have only temp_sum. For all the remaining cases u will have max_sum wich u have stored in first iteration to verify which is big. So we added the condition i==0 && j==0 instead of assigning max_sum to a garbage value initially.

ernestea + 2 comments int max_sum = 0; for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { int temp_sum = 0; // top row temp_sum += arr[i][j]; temp_sum += arr[i][j+1]; temp_sum += arr[i][j+2]; //middle temp_sum += arr[i+1][j+1]; //bottom row temp_sum += arr[i+2][j]; temp_sum += arr[i+2][j+1]; temp_sum += arr[i+2][j+2]; //if first hourglass, set as max if(temp_sum > max_sum){ max_sum = temp_sum;///this will keep it up to date } } }

moyinobey + 0 comments set max_sum to a negaive number incase tthe temp_sum value is less than 0 in the case where the temp_sum evaluates to a negative value. thanks for the code by the way.

wangzhirong57 + 0 comments you could just set i , j from 1 to 5 for (int i = 1; i< 5; i++)

then you just use arr[i][j], i, j could be +1 or -1 this will much easier to understand

lazermazer + 4 comments i wrote mine just like you before reading this, but it fails on test case 3 and 7

imsunil266 + 0 comments [deleted]imsunil266 + 0 comments in testcase 3 there is 2 less element in last row. did you notice?

umeshce2014 + 1 comment [deleted]umeshce2014 + 0 comments `int maxSum = Integer.MIN_VALUE; for(int i = 0; i <= arr.length -3; i++){ for(int j = 0; j<= arr[i].length -3; j++){ int perHrGlassSum = Integer.MIN_VALUE; perHrGlassSum = 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(perHrGlassSum > maxSum){ maxSum = perHrGlassSum; } } } return maxSum; Try this.`

nefarious090 + 1 comment for me also its failing the test case 3 and 7. When i download the test case input and check its missing some last few numbers. We cant even hard code those values if its zero to submit cause more than test case is failing. Dont know how to fix it and submit it

guptapakhi08 + 0 comments exactly my problem! idk how other people have gotten their test cases passes

shubhamlpu2016 + 1 comment could you please explain me why are you iterate the i and j till 3.

guptapakhi08 + 0 comments because the hourglass has 3 rows ans 3 columns

mohamedagamy215 + 0 comments Great and clear

pgmreddy + 0 comments Again almost beautiful code. temp_sum += many times, which can be removed. Conditions look complex not required.

sarthakgupta98 + 1 comment Can you please help me understand the logic behind it

pgmreddy + 0 comments

myclockwork + 0 comments Well done. I like the clean code. I had to figure out the hard way to set the first hourglass as max for negative values.

170040724_s30 + 0 comments At first i have also tried the same idea only.but max is not working incase of negative values.....nd then i went for sorting and its works for all test cases......

kondayinG + 0 comments Good one. Arrays.sort(); could be replaced with the following (less time complexity) int highestSum = Integer.MIN_VALUE;

JKDos + 0 comments This one is pure genius

boleke + 1 comment Any thoughts?..

`int hourGlassSum=0; int max =-100; for(int i=0; i < 6; i++){ for(int j=0; j < 6; j++){ arr[i][j] = in.nextInt(); } } for(int k=0; k<4;k++){ for(int l=0;l<4;l++){ for(int m=0;m<3;m++){ for(int n=0;n<3;n++){ if(m==1 && (n==0 || n==2)) continue; hourGlassSum+=arr[k+m][l+n]; } } if(max<hourGlassSum) max = hourGlassSum; hourGlassSum=0; } } System.out.println(max);`

JKDos + 1 comment I just woke up, so I'm not in the mood to read code fully, but seeing all those

`for loops`

makes my head spin. Is that a good idea to nest so many?karananandkk + 1 comment No using many for loops causes worst time complexity.

Thiez + 1 comment The two innermost loops always result in nine additions, regardless of the size of the multidimensional array. There is absolutely

*no*difference in "time complexity" when doing something like the following instead of the nested loops:hourGlassSum = arr[k][l] + arr[k][l+1] + arr[k][l+2] + arr[k+1][l+1] + arr[k+2][l] + arr[k+2][l+1] + arr[k+2][l+2];

The source code provided by boleke, when modified to accept arrays of various sizes, runs in O(n).

karananandkk + 1 comment Here you are right.But in common usage of more for loops will not optimize the code.It will result in worst time complexity

robertwilk + 1 comment Pretty certain he's wrong no matter which way you look at it. This solution cannot be

*O(n)*. There are 16 hourglasses which need to be summed. It's not fate that*(n-2)^2 = 16*.edoquendo1314 + 0 comments He's definitely wrong each loop runs n times he has 6 loops that's already O(n^4) + the O(n^2) also for each loop he's using a linear approach which also kills his time complexity

sourav_raychaud1 + 1 comment HAHA, I did the same too..... The most time saving code!!! This is truly the best one!!!

saiful007 + 0 comments same here

HAAdams + 0 comments [deleted]denis_zhuravlov + 0 comments u don't need to sort list

print max(sum)

kundhan007 + 0 comments super bro

C_Nanayakkara + 1 comment Chould you please explane about "Arrays.sort(sum)"

robertwilk + 1 comment Arrays is a utility class for arrays in Java. Sort sorts an array. You actaully don't need to store the individual sums of the hourglasses but if you did you could find the max in less time than it takes to sort the array by iterating the elements keeping track of the largest.

C_Nanayakkara + 0 comments thank you.

Ricky127 + 0 comments I used various if else to check for -negative condition. My logic was giving highest positve number and lowest negative number. but if you put all the results in array and then sort you will get your answer, as mentioned by abhi007tyagi. Thanks

stonedonkey + 1 comment It's simple but very bound to this specific case, if the size of the input was changed you would it would result in a near rewrite.

I like the solutions below that have two sets of loops, those would be easier to extend to new matrix sizes with little code change and are still fairly simple to read.

robertwilk + 0 comments Wouldn't really result in a "near rewrite". Considering, for this problem, an hourglass is well-defined to be contained within a 3x3 matrix you'd simply change the bound to

*n-2*rather than hard-coding*4*(if that's the route you went).

ramesh_l + 1 comment How about a simple boolean check to set first calculated sum as max value.

`int max = 0; boolean notSet = true; for(int i=0;i<4;i++) { for(int j=0;j<4;j++){ 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(notSet){ max = sum; notSet = false; } else if(sum > max){ max = sum; } } } System.out.println(max);`

HeaTx + 0 comments max can't be equal 0 you're missing when they're negative values in the matrix

nrajan + 1 comment Isn't this solution is missing 2 elements for each hourglass ??

arr[i+1][j];

arr[i+1][j+2]

Thiez + 0 comments Right now the hourglass looks like this:

XXX X XXX

With your suggestion it would look like this:

XXX XXX XXX

I think the first one looks more like an hourglass than the second one :-)

sxsarkar + 1 comment I think I finally found how to do bubble sort for 2D array and looks like better than doing Array.sort which does no show the true bubble sort algorithm.

`int arrayStoreVal[][]= new int[4][4]; /* I know there are 16 values */ /* 4x4 16 Dimensions */ for(int x=0; x < 4; x++){ for(int y=0; y < 4; y++){ arrayStoreVal[x][y] = arr[x][y] + arr[x][y+1] + arr[x][y+2] + arr[x+1][y+1] + arr[x+2][y] + arr[x+2][y+1] + arr[x+2][y+2]; } } for(int i = 0; i < arrayStoreVal.length; i++){ for(int j = 0; j < arrayStoreVal.length-1; j++){ for(int k = 0; k < arrayStoreVal.length-1; k++){ if(arrayStoreVal[i][k]>arrayStoreVal[i][k+1]){ int temp = arrayStoreVal[i][k]; arrayStoreVal[i][k] = arrayStoreVal[i][k+1]; arrayStoreVal[i][k+1] = temp; } } } } System.out.println(arrayStoreVal[arrayStoreVal.length-1][arrayStoreVal.length-1]);`

pak_developer + 1 comment i dont understand this code...

lackova_cngroup + 0 comments I do undestand the code, I just don't understand why. I bet custom sort of an array wont't be more efficient than the built-in sort in Arrays. What's more, there's no need to store all sums in the array, the max value can be stored in one variable and re-set if counted sum exceeds its value. (My solution did not pass the 3rd test (with negative numbers in input array) for the first time, because I had initialized

**int max = 0**, so I changed it to**Integer max = null**and checked it when used in comparison.)

se_anilp + 0 comments its awesome!!

rishavk171 + 0 comments this is saying arra out of index

mradosovic + 0 comments You are a genius! I would just add diferent loop so that it can do longer arrays. For example: int i=0;i

aravindputrevu + 0 comments i thought exactly like you. WOW...

Markoni + 0 comments Hey super ! But instead of sorting array. I've used simple loop to play with it a little longer ;)

int max = result[0]; for(int i=1; i < result.length; i++){ if(result[i] > max) max = result[i]; } System.out.println(max);

poojakupsad + 0 comments where have u initialized array?

harshit2470190 + 0 comments Why do you want to store all the sums where you just need to print out the maximum sum? It'll save both the memory as well as the sorting running time.

agodfrey3 + 0 comments Good solution, but you don't need to keep track of all sums; you just need to keep track of the largest. If you set a "maxSum" variable, and only update it when currrSum > maxSum, you can eliminate the need for sorting ( which takes time ) as well as the sum array of size 16 ( which takes up space/memory ). (The variable h becomes unnecessary, too).

NAVEENREDDY09 + 0 comments Sorry I missed negative test case , I am working on it

boobiesboob + 0 comments wow. I was sitting soooo long on the solution and did not get it. has the idea but just could not realize it. looks really nice!

jaihoon + 0 comments [deleted]Feenis + 0 comments I did something similar, but without the sum array.

int max = Integer.MIN_VALUE; for(int i=0; i+2 < arr.length; i++) { for(int j=0; j+2 < arr[0].length; j++) { 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][down+2]; max = Math.max(sum,max); } } System.out.println(max);

aboelmagd + 0 comments i think its missing a couple of test cases, there are definitley cases that are not going to hold according to this :)

ScienceD + 0 comments Why do we need sum array if we only need 1 sum - biggest. Pointless waste of memory! Also array sorting is waste of computation time too.

sujoyduttajad + 0 comments I cannot understand the function Arrays.sort(sum) can you please explain me

sujoyduttajad + 0 comments Why you take 16 and 15 as size of the array bcoz when I used 20 & 19 it showed error.

mahmood1367 + 2 comments I know that the order is higher than computing hourglass sum without for loops . I just wanted to say there is another way.

`int maxSum = Integer.MIN_VALUE ; //shift a 3*3 window through the 2D-array and calculate hourGlassSum of it for(int i=0; i < 4; i++){ for(int j=0; j < 4; j++){ maxSum = Math.max(hourGlassSum(arr,i,j),maxSum); } } System.out.println(maxSum); } public static int hourGlassSum(int[][] arr,int x,int y){ int i , j ,hourGlass = 0; //compute sum of all items in the window for (i = x; i < x + 3; i++) { for (j = y; j < y + 3; j++) { hourGlass += arr[i][j]; } } //exclude numbers which are not in the hour glass but has been added in last step hourGlass -= arr[x+1][y]; hourGlass -= arr[x + 1][y + 2]; return hourGlass; }`

mahmood1367 + 0 comments [deleted]deoramanas + 0 comments working on all testcases?

nazimhmd4 + 0 comments Wow its short and simple

chandrashekhar22 + 0 comments This is the best solution

Shebelby + 0 comments this one is a win, especially since it's an excersize about arrays. using an arry to store sums and Arrays.sort is very smart.

aleesha_kanwal + 0 comments why sum[15] ?

SaraDN + 0 comments Omg, I didn't think about using sorting! That's such an interesting method!

Corvo17 + 0 comments Cool Solution BRO

Corvo17 + 0 comments This is the best solution I think bro

nelpontejos + 0 comments mine is very long, this is better, thanks

manishjoshi93 + 0 comments my c# solution

int []sum = new int[16]; int h = 0; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { sum[h] = 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]; h++; } } Array.Sort(sum); Console.WriteLine(sum[15]);

nlad11 + 0 comments This solution does not satisfy all test cases.

ernestea + 1 comment int sum = 0; int h = 0; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { int sumTemp = 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(sumTemp>sum){sum=sumTemp;}//this will keep sum up to date } } System.out.println(sum);

broser + 0 comments This is good but it fails a few test cases because in some arrays with negative values, the largest sum of an hourglass is actually less than 0 (ex. -6 or -19).

Kind of overkill but you can initialize sum to be Int32.MinValue to be sure your sum will always be updated.

angelw1961 + 0 comments Can you explain the process in this solution? new to this the 2d Array is really just confusing me.

ml2963 + 0 comments This is my solution. I feel like the use of a new sum array is not needed. The reason why max = -64 is because each term in the 2D array is: -9 <= A[i][j] <= 9. Since an hourglass has 7 terms, the lowest sum possible is -63. Therefore, the sum will always be greater than the max and change the max to be the greatest sum.

`int sum, max = -64; for (int i = 0; i < 4; i++){ for (int j = 0; j < 4; j++){ 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 (sum > max){ max = sum; } } } System.out.println(max);`

If there is any way to make my code more efficient or clearer to understand, please let me know. Thanks!

Namrata777 + 0 comments I tried this logic, but it gives ArrayOutOfBoundException for the sum[h] statement ..

[deleted] + 0 comments Nice logic but this solution doesn't work for a matrix of negative numbers

it_beast + 0 comments Nice

Barjinder_paul + 0 comments Save that space of extra array out there!!

int maxSum=INT_MIN,sum=0; for (int i = 0; i < 4; i++) { for (int j=0; j<4;j++) { 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(sum>maxSum) maxSum=sum; sum=0; }} cout<<maxSum;

aheza007 + 0 comments Extra storage and sorting. why not keep the max sum only? for example if you're using Java you could use the Math.max(a,b) function.

prashantdixit82 + 0 comments Why you are running the loop less than 4? Please explain your code.

pgmreddy + 0 comments Almost beautiful code. I came up with up with similar looking, but more similar looking to the one given as 'Featured Solutions' in the Editorial, which is dead beautiful.

raju_muke + 0 comments why are you using extra space for array ? I am doing the same without using extra space

int max = Integer.MIN_VALUE,sum=0; for(int i=0;i<4;i++){

`for(int j=0;j<4;j++){ 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(sum>max){ max=sum; } } } System.out.println(max);`

rajeevmjmdr + 0 comments `int A=0,temp=-63,sum=0; while(A<4){ int B=0; while(B<4){ int C=A; while(C<A+3){ int D=B; while(D<B+3){ if(C==A+1 && D==B) { } else if(C==A+1 && D==B+2){ } else{ sum +=arr[C][D]; } D++; } C++; } if(sum > temp){ temp = sum ; } sum = 0; B++; } A++; } System.out.println(temp); scanner.close(); }`

}

darshan_hegde_dh + 0 comments [deleted]darshan_hegde_dh + 0 comments *i,j=0,0 hsum=list() maxsum,hrsum=0,0 for i in range(4): for j in range(4): hrsum=sum(arr[i][j:j+3])+arr[i+1][j+1]+sum(arr[i+2][j:j+3]) hsum.append(hrsum) #print(hrsum) for debugg hrsum=0

print(max(hsum)*)

this is more concise.

Sonymr555 + 0 comments why i and j<4 ?

se_roope + 1 comment `for i in range(4): for j in range(4): hourglasses.append(sum(arr[j][i:i + 3]) + arr[j + 1][i + 1] + sum(arr[j + 2][i:i + 3])) print(max(hourglasses))`

jacqueline3749 + 0 comments I got an index error.

SuperHak + 0 comments Here is an imporved solution without using an additional Array.

public static void hourGlass(int[][] arr){ int max = Integer.MIN_VALUE, sum = 0; for(int i = 0; i < 4; i++){ for(int j = 0; j < 4; j++){ 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(sum > max){max = sum;} } } System.out.println(max); }

yash9274 + 0 comments nice solution sir... very implementable and easy to understand..

rajsinha1a + 0 comments Perfect code for the problem. Easy to understand,compact & concise.

Amine_Kihal + 0 comments Coding with style! You get the best time complexity! Good job!

BeardedOwl + 0 comments Awesome man!!!!

birozso + 0 comments mine was the same except the sum function , that is great!

_atse + 15 comments Python solution:

res = [] for x in range(0, 4): for y in range(0, 4): s = sum(arr[x][y:y+3]) + arr[x+1][y+1] + sum(arr[x+2][y:y+3]) res.append(s) print(max(res))

rookiesix + 2 comments Hi, could you explain why it's

`sum(arr[x][y:y+3]) + arr[x+1][y+1] + sum(arr[x+2][y:y+3])`

My code is similar but just reversed, and I cannot understand why I'm reversed

`test = [] for x in xrange(4): for y in xrange(4): m = -100000 total = arr[x][y] + arr[x+1][y] + arr[x+2][y] + arr[x+1][y+1] + arr[x][y+2] + arr[x+1][y+2] + arr[x+2][y+2] if total > m: m = total test.append(m) print max(test)`

of course it didn't work. but why not? Am I not taking the top three numbers, then the middle one, and then the bottom three numbers?

Xarmanla + 1 comment You rotated the hourglass to rest on its side.

Nineteen99 + 2 comments Why does it seem that the x and y axes are reversed? Wouldn't the x axis be left and right and the y axis be up and down on the grid?

Xarmanla + 0 comments Ths names x and y are arbitrary. What matters is which is the outer loop and which is the inner loop.

cmbaskerville + 1 comment It seems like the way it is defined the coordinate in arr are arr[down][right]. This is contrary to my linear algebra coordinate system thinking of (left/right, up/down).

aaron_brandhagen + 0 comments We're just applying algebraic concepts to the code.

Point is, that is the obvious way to get an index from a list of lists (call the index of the list in the list first, then one or more of it's items)

TMWP01 + 1 comment This is pretty close to what I did. One minor nit: you should declare variables outside your loops and then assign inside your loops as a best practice. Memory allocation is more expensive then memory assignment according to a book I read. In this case, we don't notice the difference (probably). But in some programs, this minor change will boost performance considerably.

hsu_ryan + 1 comment are you referring to the variable "res"?

konrad_zenczak + 0 comments 'res' is okay, because we initiate a list before we start appending to it through the loop. Pretty sure TMWP01 responded to another comment, the one where 'm= -10000' is initiated inside an inner loop. So basically it's getting initialized multiple times, in each loop, instead just once - before the loop.

prototype625 + 0 comments [deleted]shabieh2 + 0 comments such an elegant solution!

makes me love python more

HeaTx + 5 comments My Python solution:

max = -100 for i in range(4): for j in range(4): sum = arr[i+1][j+1] for x in range(3): sum += arr[i][j+x] + arr[i+2][j+x] if sum > max: max = sum print(max)

majiyd + 0 comments why are you using range(4)?

majiyd + 0 comments No worries, i got it

karthik19894 + 1 comment Can u please explain, how did u arrive at the expression for sum+=arr[i][j+x]+arr[i+2][j+x]? I can understand that its the sum of values at specific indices as per the pattern. But how did u arrive at this expression?Is there any shortcuts or methods to arrive at the polynomial expression?

saurabhbharti9 + 0 comments sum=arr[i][j+x] -> sums the top row of the hour glass sum=arr[i+2][j+x] -> sums the bottom row of the hourglass. sum = arr[i+1][j+1] -> sums the middle row. arr[1 2 3 4 5 6 7 8 9] if i=0,j=0,x=0 calculate and increment.

brunolemos_ssa + 2 comments what you people think about this:

`my_hourglasses = list() for i in range(0,4): for j in range(0,4): hourglass = list() hourglass += arr[i][j:j+3] hourglass.append(arr[i+1][j+1]) hourglass += arr[i+2][j:j+3] my_hourglasses.append(hourglass) hourglasses_sums = [sum(item) for item in my_hourglasses] print(max(hourglasses_sums))`

balasaheb_kiswe + 1 comment You made look it like very easy which is not very easy problem to solve. why the range is between (0, 4)? explaination will be very helpful

efimius + 0 comments becuase matrix moves 4 times every side

peddibalabhavani + 0 comments why we get list out of range for above program

bhavani1ans + 0 comments why are u take max =-100

Naveen_DS + 0 comments [deleted]mz9201ju + 0 comments Sexy solution. Love it

denonjugush + 0 comments Cool, especially the pythonic approach.

n_okroshiashvili + 0 comments That is perfect solution!

andre_rua_pires + 0 comments my python solution

if

**name**== '**main**': arr = []`for _ in range(6): arr.append(list(map(int, input().rstrip().split()))) m = [] for i in range(len(arr)): for j in range(len(arr[i])): try: m.append(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]])) except IndexError as e: continue`

print(max(m))

shubhamlpu2016 + 0 comments why are you taking the range from 0 to 4. why not 0 to 3.

adan_medina1 + 0 comments Sorry for the basic question, but are you importing "arr" from somewhere? I considered using a numpy array for this but am unsure if there is another method with the standard library.

ShixiangWang + 1 comment Good.

I think digit

`4`

can be change to`len(arr)-2`

, applying solution to any square matrix.rakshitsai0708 + 0 comments but dude why ? i still don't get it why are we using len(arr)-2 or 4.

ShixiangWang + 0 comments Good.

I think digit

`4`

can be change to`len(arr)-2`

, applying solution to any square matrix.jacqueline3749 + 0 comments `IndexError: list index out of rang`

I got this message. What do I do?

multi_thinker_1 + 2 comments I've a general question, the tab "Discussions" should be for discussing things but often i see people sharing their solutions which expose all the code and make the cheating possible, isn't there anyone like moderator or isn't there any rule that prevent such things? it's a total failure if a person doesn't learn on its own and copy paste someone's "posted" code and pass the challange.

edlaierii + 1 comment I upvoted this, I think a person should pass a certain percentage say before seeing other people's solutions. I do however like to compare my code with other's to see if there is some other more efficient way to go about a solution. But so far (having been on another coding puzzle/golf site) my coding is usually better than others.

multi_thinker_1 + 0 comments for comparing your code and looking into others code hackerrand provides excellent feature, on "Leaderboard" tab you can see people who submitted their codes along with their name and country, you can look into as many submissions as you want when you have complete that challange by yourself first to unlock this feature..

"BUT" having code comparison, or code/logic "exposed" in comment section is kind of what we can call open "cheating", it should be monitored.

Redliquid + 0 comments Isn't that up to each individual person? I learn alot by looking at other peoples codes and dissecting each line of code untill i understand the whole.

Why do you care if other people "cheat"?

kvpratama + 3 comments Here is my solution in java:

`int max = -64, temp; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { temp = 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 (temp > max){ max = temp; } } } System.out.println(max);`

cold_steel_br + 2 comments int max = -64, temp;

Should be:

int max = Integer.MIN_VALUE;

int currentSum;

HeaTx + 0 comments the lowest value could be -63 that's -9*7 (7 values of an hourglass)

tdsamardzhiev89 + 0 comments I agree with cold_steel_br. Magic numbers make code less readable and harder to change.

rutul_1993 + 1 comment Hi,

i don't know why you have set max=-64?

HeaTx + 0 comments because the lowest value could be -63, when considering the negative numbers (value could be from -9 to 9) that's -9*7 (7 values of an hourglass)

taishiyade + 1 comment max = -64 This is so smart! Thank you! This is so helpfull!

dlj0613 + 0 comments If you're coding in Java, you could use max = Integer.MIN_VALUE.

parkercancode + 2 comments For all struggling on the negative examples(#3 and #7), here is how to fix it in layman's terms. Set your variable for the highest sum to the lowest value a sum could be: -63. This makes it work because during the check if the sum of the current hourglass is greater than the current highest sum, it is failing because that negative number is lower than zero.

Bad_Jim + 1 comment Thanks dude. I feel like such a fool, not reading the program constraints properly.

parkercancode + 0 comments Don't worry about it- I do it all the time.

arustagi99 + 0 comments tysm

Sort 1058 Discussions, By:

Please Login in order to post a comment