abhi007tyagi 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 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 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 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 Yes, it would be nice in Arrays, Algorithm section.
abcoder4 #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 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 In code block this code is running but not here
gandivenkatesh11 In that case instesd of using 4 we can use n-2 in loop
rajsinha1a 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 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 [deleted]HAAdams 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 [deleted]ppdusa 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 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 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 //scala object Solution { var maxArray = Array.ofDim[Int](3, 3) var maxSum = -50
// To print Array if you wantdef 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 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 What is n?
guptapakhi08 It is the size of the array.
sanjeet_skg if you take max=0, then test case 3 and 8 will fail.
abhijit25k same is happening for me as well... How to work around that?
sanjeet_skg 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 Thanks for explaining... Because of -ve elements taking zero will fail for two testcases... Now got it..
suryodaya_s44 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 thanks bhai was stuck thinking every thing is alright then saw this changed the max =-1000 and worked as everything was working perfectly.
prakharshukla201 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 [deleted]anshuman854 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 It works! Good solution and understandable
monisms15 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 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 then the i and j loop will run till i,j < n-2
amiteshrajvaidy1 for nxn matrix the loops for both row and column will go upto n-2
kasusaland that is more complex .. but is this circumstances this is just fine
teckvui78 [deleted]
maximshen 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 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 Determining all sums is in O(n).
robertwilk 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 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 I assumed fixed-size hourglasses, and my
nis the number of entries in the matrix, not the dimensions of the matrix.
dseelin 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 Most clear solution Ive seen. Cheers
a_shivani63 could you please explain me why you have taken the condition i==0 && j==0 in if condition?
priyankaagrawal2 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 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 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 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 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 i wrote mine just like you before reading this, but it fails on test case 3 and 7
imsunil266 [deleted]imsunil266 in testcase 3 there is 2 less element in last row. did you notice?
umeshce2014 [deleted]umeshce2014 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 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 exactly my problem! idk how other people have gotten their test cases passes
shubhamlpu2016 could you please explain me why are you iterate the i and j till 3.
guptapakhi08 because the hourglass has 3 rows ans 3 columns
mohamedagamy215 Great and clear
pgmreddy Again almost beautiful code. temp_sum += many times, which can be removed. Conditions look complex not required.
sarthakgupta98 Can you please help me understand the logic behind it
myclockwork 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 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 Good one. Arrays.sort(); could be replaced with the following (less time complexity) int highestSum = Integer.MIN_VALUE;
JKDos This one is pure genius
boleke 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 I just woke up, so I'm not in the mood to read code fully, but seeing all those
for loopsmakes my head spin. Is that a good idea to nest so many?
karananandkk No using many for loops causes worst time complexity.
Thiez 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 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 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 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 HAHA, I did the same too..... The most time saving code!!! This is truly the best one!!!
saiful007 same here
HAAdams [deleted]denis_zhuravlov u don't need to sort list
print max(sum)
kundhan007 super bro
C_Nanayakkara Chould you please explane about "Arrays.sort(sum)"
robertwilk 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 thank you.
Ricky127 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 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 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 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 max can't be equal 0 you're missing when they're negative values in the matrix
sxsarkar 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 i dont understand this code...
lackova_cngroup 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 its awesome!!
rishavk171 this is saying arra out of index
mradosovic You are a genius! I would just add diferent loop so that it can do longer arrays. For example: int i=0;i
aravindputrevu i thought exactly like you. WOW...
Markoni 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 where have u initialized array?
harshit2470190 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 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 Sorry I missed negative test case , I am working on it
boobiesboob 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 [deleted]Feenis 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 i think its missing a couple of test cases, there are definitley cases that are not going to hold according to this :)
ScienceD 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 I cannot understand the function Arrays.sort(sum) can you please explain me
sujoyduttajad Why you take 16 and 15 as size of the array bcoz when I used 20 & 19 it showed error.
mahmood1367 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 [deleted]deoramanas working on all testcases?
nazimhmd4 Wow its short and simple
chandrashekhar22 This is the best solution
Shebelby 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 why sum[15] ?
SaraDN Omg, I didn't think about using sorting! That's such an interesting method!
Corvo17 Cool Solution BRO
Corvo17 This is the best solution I think bro
nelpontejos mine is very long, this is better, thanks
manishjoshi93 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 This solution does not satisfy all test cases.
ernestea 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 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 Can you explain the process in this solution? new to this the 2d Array is really just confusing me.
ml2963 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 I tried this logic, but it gives ArrayOutOfBoundException for the sum[h] statement ..
[deleted] Nice logic but this solution doesn't work for a matrix of negative numbers
it_beast Nice
Barjinder_paul 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 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 Why you are running the loop less than 4? Please explain your code.
pgmreddy 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 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 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 [deleted]darshan_hegde_dh *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 why i and j<4 ?
se_roope 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 I got an index error.
SuperHak 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 nice solution sir... very implementable and easy to understand..
rajsinha1a Perfect code for the problem. Easy to understand,compact & concise.
Amine_Kihal Coding with style! You get the best time complexity! Good job!
BeardedOwl Awesome man!!!!
birozso mine was the same except the sum function , that is great!
_atse 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 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 You rotated the hourglass to rest on its side.
Nineteen99 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 Ths names x and y are arbitrary. What matters is which is the outer loop and which is the inner loop.
cmbaskerville 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 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 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 are you referring to the variable "res"?
konrad_zenczak '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 [deleted]shabieh2 such an elegant solution!
makes me love python more
HeaTx 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 why are you using range(4)?
majiyd No worries, i got it
karthik19894 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 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 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 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 becuase matrix moves 4 times every side
peddibalabhavani why we get list out of range for above program
bhavani1ans why are u take max =-100
Naveen_DS [deleted]
mz9201ju Sexy solution. Love it
denonjugush Cool, especially the pythonic approach.
n_okroshiashvili That is perfect solution!
andre_rua_pires 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: continueprint(max(m))
shubhamlpu2016 why are you taking the range from 0 to 4. why not 0 to 3.
adan_medina1 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 Good.
I think digit
4can be change tolen(arr)-2, applying solution to any square matrix.rakshitsai0708 but dude why ? i still don't get it why are we using len(arr)-2 or 4.
ShixiangWang Good.
I think digit
4can be change tolen(arr)-2, applying solution to any square matrix.jacqueline3749 IndexError: list index out of rangI got this message. What do I do?
multi_thinker_1 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 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 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 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 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 int max = -64, temp;
Should be:
int max = Integer.MIN_VALUE;
int currentSum;
HeaTx the lowest value could be -63 that's -9*7 (7 values of an hourglass)
tdsamardzhiev89 I agree with cold_steel_br. Magic numbers make code less readable and harder to change.
rutul_1993 Hi,
i don't know why you have set max=-64?
HeaTx 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 max = -64 This is so smart! Thank you! This is so helpfull!
dlj0613 If you're coding in Java, you could use max = Integer.MIN_VALUE.
parkercancode 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 Thanks dude. I feel like such a fool, not reading the program constraints properly.
parkercancode Don't worry about it- I do it all the time.
arustagi99 tysm
Sort 1058 Discussions, By:
Please Login in order to post a comment