thegeeksam if you want to pass test Case 3 and 5 dont initialize max value to 0.
madulidjpAsked to answer yeah. you should initialize the max value to the value of the first hourglass.
ronak319 you can also set any large negative value also. Then no need to caluculate first hourglass separately.
for e.g , max_value = -99999;
ivdekov This is helpful, thank you. I used Integer.MIN_VALUE;
ldaicich Just a very silly thing, but you can also use Short values for the purpose of this problem, it doesn't have to be necessarily an Integer. Just for using less memory. :)
bin_zhao10 I think the input variables are defined as primitive type int.
abhilashupare Guys we also have one more alternative, with the help of flag we can achieve it,
if (flag) {
max = sum;
flag = false;
}
if (max < sum) {
max = sum;
}
MonisKhan will it not give a compilation error i.e max is not initialized or something like that?
successhawk Using your logic, you could use the type byte.
TechieToby Given the constraint in the question (-9 <= arr[i][j] <= 9 and 0 <= i,j <= 5), I used the possible maximum negative value to initialize my max value (-9 * 6 = -54).
sammurphych max negative value is -63 (-9 * 7)
amanagarwal2189 anything less than -54.
ghaderi_amin For python initialize with: -9223372036854775807
mudit2jain It passed the testcases but why it doesn't runs when initialized to zero?
prajapple If the sums of hourglasses are all negative , and if u have taken your max variable initilized to zero and calculate the max with refrence to 0 obviously you will be returning 0 as the answer which is wrong . So its better to initilize with Integer.MIN_VALUE to a variable to which will be storing a max value .
kapil18pandey thanks mate... helped a lot!!!
balajilitsv Or initialize it to any value less than -63, because the input values of the array ranges from -9 to +9. So a hour glass can contain a maximum of 7 times -9, which sums up to -63. Any value greater than -64 can be accepted to swap the max variable, right!
HotIce! Try this man!
1l0v3c0d3 Actually, -63 will work too.
balajilitsv Or initialize it to any value less than -63, because the input values of the array ranges from -9 to +9. So a hour glass can contain a maximum of 7 times -9, which sums up to -63. Any value greater than -64 can be accepted to swap the max variable, right!
HotIce!
VishalVasistha Taking max value as integer.MIN_VALUE is also correct however max can also be sumArray[0] (the array of sum of hourglasses) .
jaismeenkaur Thanks ! That helped.
tfloresu Zero is considered to be a positive number. If all the hour glasse's totals are negative they wont beat your zero.
pratikkejriwal instead of using min value of integer, you can just initialize it to -63 as it is clearly mentioned that the values cannot be less than -9. So -9*7=-63
mondayrain It's worth noting that the description clearly states that the input will be -9 <= R <= 9. This means that the smallest possible value will be -9*7 (as there are 7 elements in an hourglass). So one can just initialize the max value to -63 :)
Eschatite [deleted]aman1324 Yes. In case the constraints are not there, use Integer.MIN_VALUE.
anuragpugalia11 yes it worked. thanks
architvis This is were I messed up, I initialized max value to -9. Thanks, didn't relize were I messed up at until reading your comment.
kaasib Simply set it to null and use type specific comparison to assign first sum.
anshulkataria4 why do we need to set max to -63 or to any such value ?
t_egginton because if you initialise to zero, if the max hourglass sum is negative then it will not overwrite the zero value. best to either initialise it with the value of the first hourglass (slightly more elegent in my opinion) or a large negative value. 63 is significant because it is not possible to get a sum less than that under the constraints given.
nancy345 hello sir! i want to know that if we want to do this programming in c so what programe is used from the starting because my basic in c and c++ is not clear and also i m not familiar with its operation so kindly send me a complete programe based on it in C. thanku
mdumlupinar [deleted]
amulya_123 why should we initialize max value to large negative value?
supertrens because if you initialise to zero, if the max hourglass sum is negative then it will not overwrite the zero value. since 0 will be greater to any negative number. What I do is save the first hourglass sum as teh finalSum and update it when/if the next ones are bigger.
sugsurnitsin what is the hour glass
ernestns [deleted]
shrewga The least no. possible is -9 * 7 = -63. We can also initialize it to that. :)
meerakrish Thanks
shrewga [deleted]
varun_1995 int max = Integer.MIN_VALUE;
abhiram_n actually -63 is enough.Since 7 slots having a minimum value of -9 in each would turn out to a maximum negative of -7*9=-63
gmoralesc I used Number.NEGATIVE_INFINITY with Javascript
nikhil_j_kurien you can set it to integer.MIN_VALUE
GomathiN You can use -63 as max value because it is stated in condition that a[i][j] is between -9 and + 9
vamsi5 you know max_value = -63 would do just fine. because the lowest maximum number that can be achieved with given constraints is -63. The given constraints for element in array is [-9,9] so the max an hour glass with all -9s would give (-9)*(7(no_of elements in hour glass)) = -63
sangeetharaj may i know what is the reason behind this? why we have to initiliza ma_value = -9999 or -63
samuelpaulc since the hourglass with smallest sum is -63 when all values in hourglass are -9
nithindevn [deleted]
shiva_nk -63 would be enough
deepak111224 bro you can just set max value to -9 * 7 = -63 cause it can be the most small value of hourglass acording to question
chaudharymayank1 even -63 can work fine
alex_wallish No need to set max value that low. It will not possibly be any lower than 7*9 so you can simply initialize it to 63.
david_rodriguez2 perhaps -9*7 is enough, though
harminder_oassan you could just use one less than the minimum possible value of an hourglass, which is -64.
balajilitsv Or initialize it to any value less than -63, because the input values of the array ranges from -9 to +9. So a hour glass can contain a maximum of 7 times -9, which sums up to -63. Any value greater than -64 can be accepted to swap the max variable, right!
HotIce!
mosjabr since the least sum is -63 (when all elements are -9), you can initialize it to be -63
_withoutwax Or you can use
float('-inf')
which gives you the largest negative value.
ghaderi_amin Worked like a charm. Thanks. I didnt know we can compare floats and integers.
dv1pr I set max = nil and then checked if max was nil before setting max to the total with an or conditional
e.g., max = total if max == nil || total > max
aaliagab85 short mayor=-63;
edward_cerveriz1 If you are writing in Java, you can actually use max_value= Integer.MIN_VALUE; to get the lowest signed interger value in case -99999 isn't enough.
jordancg91 The problem specifies that arr[i][j] values are only between -9 and 9, so the minSum for any hourglass can be -63, specifing the initial max_value = -64 will ensure that any sum will be greater
jonmcclung [deleted]mdumlupinar you can set -63 for the initial value of the max variable, because the possible minimum value of a hourglass can up to be -63. According to the given restrictions, the minimum hourglass can have maximum seven -9. So, this is the initial number for us: 7x-9=-63.
nancy345 how to do this task in C???
mdumlupinar sorry, i am not familiar with c language.
azheruddin617mr1 int main() { int matrix[6][6]; for(int i = 0;i < 6;i++) { for(int j = 0;j < 6;j++) { scanf("%d",&matrix[i][j]); } } int maxsum = -1000,jj = 0; for(int i = 0;i < 4;i++) { int sum = 0; for(int j = jj;j < jj+3;j++) { sum += matrix[i][j]; if(j==jj) sum += matrix[i+1][jj+1]; sum += matrix[i+2][j]; } jj = (jj < 3) ? jj+1 : 0; if(sum > maxsum) maxsum = sum; if(jj != 0) i--; } printf("%d",maxsum); return 0; }
dattagates why have u assigned maxsum=-1000 ? can u elobarate
azheruddin617mr1 the inputs also given in negitive....
flash793 The constraints given say that any element in the array will be at least -9 and be at most 9. The smallest hourglass sum will be -9*7 = -63. So in this case, you just need to initialize max sum to be any value <= -63.
meerakrish why did you use j=jj
Sarath_95 what the below statement does in the code?
if(jj != 0) i--;
franklinvidal jj = (jj < 3) ? jj+1 : 0; // set 0 if jj(collumn pointer) set in one position which allows calculate an hourglass if(sum > maxsum) maxsum = sum; if(jj != 0) i--; // if jj is in a position where a hourglass can be calculated, the line pointer(i) continue in the same line
ragulravi1999 To run loop for same value of i with different values for j untill j maximum limit is reached
bhavgothadiya why not take -1
pa1v_kar [deleted]pa1v_kar could anyone identify the mistake
int main(){ int arr[6][6]; for(int arr_i = 0; arr_i < 6; arr_i++){ for(int arr_j = 0; arr_j < 6; arr_j++){ scanf("%d",&arr[arr_i][arr_j]); } } int sum[30]; int x=0; int arr_i,arr_j; int largest; for(arr_i=0;arr_i<3;arr_i++) { sum[x]=0; int count=0; for(arr_j=arr_i;count<3;arr_j++) { if(count==0) { sum[x]+=arr[arr_i+1][arr_j+1]; } sum[x]+=arr[arr_i][arr_j]; sum[x]+=arr[arr_i+2][arr_j]; ++count; } ++x; } largest=sum[0]; for(int i=1;i<=x;i++) { if(largest<sum[i]) largest=sum[i]; } printf("%d",largest); return 0; }
Nidheesh_P in for loop try i<4 instead of i<3
manny_capacidade Whats the reason behind i<4..Not able to get the reason.Can you explain please
fhasson91 there are 4 hourglasses vertically and 4 hourglasses horizontally
uniquechhetrii for(arr_i=0;arr_i<3;arr_i++) { sum[x]=0; int count=0; for(arr_j=arr_i;count<3;arr_j++) { if(count==0) { sum[x]+=arr[arr_i+1][arr_j+1]; } sum[x]+=arr[arr_i][arr_j]; sum[x]+=arr[arr_i+2][arr_j]; ++count; } ++x;
I didnt understand this part. Can somebody help me out in this?
chadams His algorithm is getting the middle element of the hourglass on the first pass through and then incrementing the top and bottom rows of the hourglass. He increments count to track the amount of loops needed to read a hourglass and increments x to correspond to the position in the hourglass; 0,1,2 respectively.
vigneshiyer66661 [deleted]
chernandez2 This code passes all the test cases
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> using namespace std; int main(){ vector< vector<int> > arr(6,vector<int>(6)); for(int arr_i = 0;arr_i < 6;arr_i++){ for(int arr_j = 0;arr_j < 6;arr_j++){ cin >> arr[arr_i][arr_j]; } } vector<int> res; res.reserve(18); for(unsigned int j=0; j<4;++j){ for(unsigned int i=0; i<4;++i){ res.push_back(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]); } } cout<<*max_element(res.begin(),res.end())<<endl; return 0; }
160302032CSE can anyone explain this part
res.reserve(18); for(unsigned int j=0; j<4;++j){ for(unsigned int i=0; i<4;++i){ res.push_back(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]); } } cout<<*max_element(res.begin(),res.end())<
revathymanulal - res.reserve(18) is like declaring an array of size 18 though am not sure why size 18 was choosen ,I think 16 would have done the job.
-the two for loops with contraints <4 is for the purpose of forming the hour glass (had it been <6 it would have resulted in indexing issues)
-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] these are the indexes which form an hour glass, the sum of every hour glass is calculated and push to the res
-cout<<*max_element(res.begin(),res.end()) the maximum value in res is choosen as the output
revathymanulal I used a similar approach but dint I keep on storing all of the values of hour glass instead just kept on swaping the values incase the value of new hour glass was greater than the previous one.
import sys a = [] for arr_i in xrange(6): arr_temp = map(int,raw_input().strip().split(' ')) a.append(arr_temp) max_sum =-63 for i in range(4): for j in range(4): check_sum = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1]+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2] if check_sum > max_sum: max_sum = check_sum print max_sum
tppiotrowski [deleted]
typicallucas Hi, you're including a bunch of extraneous libraries. You are just using vector, iostream, and algorithm.
The rest could be deleted :) Cheers
banerjeeunmesha I didnot include any extraneous libraries, I did my code in c++,kindly help me...thank you for your time and help my code:
include
using namespace std; void sum(int[][6]); int main() { int a[6][6]; int i,j; cout<<"enter val\n"; for(i=0;i<6;i++) { for(j=0;j<6;j++) { cin>>a[i][j]; } } sum(a); return 0; } void sum(int a[][6]) { int l=0,m=0; int i,j,max; int sum[4][4]; for(i=0,j=0;i<=3,j<=3;j++) { if(j==3) { sum[l][m]=a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1]+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2]; i++; j=-1; } else { sum[l][m]=a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1]+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2]; } m++; if(m==4) { l++; m=0; } } max=sum[0][0]; for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(sum[i][j]>=max) { max=sum[i][j]; } } } cout<<"max"<
typicallucas hi, i think you're more likely to get help if your code is more readable. Wrap your code with three back-ticks and that should help improve the
banerjeeunmesha include
using namespace std; void sum(int[][6]); int main() { int a[6][6]; int i,j; cout<<"enter val\n"; for(i=0;i<6;i++) { for(j=0;j<6;j++) { cin>>a[i][j]; } } sum(a); return 0; } void sum(int a[][6]) { int l=0,m=0; int i,j,max; int sum[4][4]; for(i=0,j=0;i<=3,j<=3;j++) { if(j==3) { sum[l][m]=a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1]+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2]; i++; j=-1; } else { sum[l][m]=a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1]+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2]; } m++; if(m==4) { l++; m=0; } } max=sum[0][0]; for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(sum[i][j]>=max) { max=sum[i][j]; } } } cout<<"max"<
banerjeeunmesha how to add back ticks? i am unable to add the pdf file as well plzz help.
typicallucas [deleted]
ramin_shahab :O Are you using all those includes?
arka_cool1996 Simple and efficient and also easy to understand . Thank you sir.
arka_cool1996 Is there any specific reason why you ran the j loop instead of the i loop first while finding the sum of the hourglass or is it just a matter of choice.
7jdeep include
int main() { int a[6][6],hg[3][3]; int i,j,x,y,sum=0,max=-63; for(i=0;i<6;i++) { for(j=0;j<6;j++) { scanf("%d",&a[i][j]); } }
for(i=0;i<4;i++) { for(j=0;j<4;j++) { for(x=i;x<i+3;x++) { for(y=j;y<j+3;y++) { if(x==i+1&&y==j) continue; else if(x==i+1&&y==j+2) continue; else hg[x][y]=a[x][y]; sum+=hg[x][y]; } } if(sum>max) { max=sum; } sum=0; } } printf("%d",max); return 0;}
fooboogoobear Holy for-loops, Batman
7jdeep [deleted]
nithishjprabhu Can u check this?
while (true) { if (mainControl + buffer > n + 1) { break; } while (true) { if (ik + buffer > n) { ik = mainControl++; jk = 0; break; } int sum = 0; for (int i = ik; i < ik + 3; i++) { if (jk + buffer > n) { jk = jk + 1; ik++; break; } for (int j = jk; j < jk + 3; j++) { int iStartIndex = ik; int jStartIndex = jk; int i1 = a[i][j]; if (i == iStartIndex || i == iStartIndex + 2) { sum = sum + i1; } else if (i == iStartIndex + 1) { iStartIndex++; jStartIndex++; if (iStartIndex == i && jStartIndex == j) { sum = sum + a[i][j]; } } } }
balajilitsv or initialize it to any value less than -63, because the input values of the array ranges from -9 to +9. So a hour glass can contain a maximum of 7 times -9, which sums up to -63. Any value greater than -64 can be accepted to swap the max variable, right!
HotIce!
prashantpx Thanks
braceman yeah you can init max value to one less than the least value possible, in this case its '-55'
mandar012 least value of sum possible = -9*7 = -63 so init max = -64
braceman thanks for the correction mandar012 and my apologies for posting such wrong ans
lose311 Why not just use
max = -63? If the whole array is-9then max will never change and output correct answer of-63jonmcclung You're right, that's the best initial value.
jonjanelle1 In this case I'd say using Integer.MIN_VALUE would be a better choice. This will make it easier to convert your algorithm to one that can be used on any size array and with different integer bounds
tOOtl It's not that important here, but by initialising to a lower value than any hourglass could have (for example -64), you'll be able to identify more easily whether a bug is causing the max value to never update (max remains at -64) or if max is updating but not to the correct value.
jonmcclung that's a good idea! whenever you can decrease the number of possible causes of a problem, that's a good thing!
aman1324 -64
leonkni10 [deleted]
malayladu Hello,
I hvae written a code in PHP and test case 5 got failed.
I am thinking that code should past all test cases. Didn't know why it failed test case 5.
PS: I didn't initialize max value to 0
kamalnamdeo You can actually set -9, which is given in problem statement. :)
jmxdbx Yeah I wonder what percentage of people (me included) wrote everything correct the first attempt, but initialized at 0 ;)
manan5439 i have 1 idea for that. first find min value from max=0arr[j][i]
suryabteja Why is that? I dont understand the logic in it.
lobheshdhakarma1 i intiliza max value -999 iam getting error can u have a c code
prakash_arya [deleted]
dban10 Good catch!!
bence_meszaros I used
int max = numeric_limits<int>::min();
baby_groot In python 3 I have used, MIN = -sys.maxsize -1
chandukotari yes, you should not intialize maximum to zero its better to intialize with a large negative number
banerjeeunmesha why am i getting timeout? my complexity is O(n^2)(for finding max)and for computing hourglass sum itts O(n)
1l0v3c0d3 Not just better, mandatory; initializing to zero is wrong.
kjadeja7 thank you
abhiram_n initialise to a negative number
NickWoodward or just test for and initialise the total to the first hourglass value
kavyasree42 i initialised max value with -63. it worked
abhinavkinshuk Just intialize max value to -63.
vash47 For Python 3, the minimum value an integer can have is:
min = -sys.maxsize -1
adit2storm then what should be taken
ksved They have stated that minimum value of the element is -9. Therefore minimum value of an hourglass is -9*7 = -63. Initialize max value to -63.
Eddy_cool //Here MAX is already 0 after that it cant pass the two testcase;
int MAX=0; int total=0; int main(){ double arr[10][10]; 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++){ total=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]; MAX=max(total,MAX); } } cout<
akshay_borse29 Initialize max_value = -63, as the minimun value of an hourglass can be only -63. No need to assign large negative value as -99999.
gpaulo42 Tks buddy. I was expend a long time to try fix it. My solution to get the minor int allowed:
int maxHourGlass = -1 * (int) Math.pow(2,32);
codextj [deleted]mkhan41 You can actually set it to -63 as we sum up 7 values at a time, and the least these values can be is -9 as per the specs.
min = -63 = -9 * 7
dgaban lol I made this mistake the first time too.
dharanaditya9 The maximum value can be a negetaive number. So initialize the max values to -63 (-9 * 7) because there are 7 elements in the hour glass and all can take the value of -9 in some case whose sumn will be the least number.
conghaikct cause the hourglass given by sum of 7 integer value from -9 to 9 . You should set max_value = -64 or lower . Sorry about my English is not good.
laurent_mundell Too late lost 5 hackos......
And now I feel dumb for not thinking of this issue earlier.
17pa1a05g0 Instead we can initialize max value to -64 as the max negative we can obtain is 7*-9
RishC Python3 answer
sum = [] for i in range(len(arr)-2): for j in range(len(arr)-2): sum.append(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]) print(max(sum))
ndakyildiz Brilliant!
madhukar_charla //Similar to this Java :) List sum = new ArrayList(); for(int i=0; i<4; i++){ for(int j=0; j<4; j++){ sum.add(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]); } } System.out.println(Collections.max(sum)); }
rishabhshairy29 why we are iterating upto 4 ??
mayank113463 coz after 4 iteration will ends the matrix .if you count 6*6 matrix and if you need only 3*3 than it will be possible only uptu 4 iterartion
9 -9 -9 1 1 1 0 -9 0 4 3 2 -9 -9 -9 1 2 3 0 0 8 6 6 0 -->>4th line 0 0 0 -2 0 0 0 0 1 2 4 0
you can iterate til 4th line because next iteration give 2 lines only
andrew_wijaya Just check the constraints in the problem statement. The algorithm is meant to solve it for a 2D array of size 4x4. Easy to generalize, just get the array dimensions and use it for iteration thresholds.
nanda_ananya Could you please explain!
gt_silva_e They are storing all the sums for every hourglass in the array/list. What I don't like about this solution is that you need more memory (allocate another array/list) and finally you need the max function, which may add extra complexity depending on the implementation. I prefer the max variable + if solution better.
serious_nick One liner in Python 3:
print(max([sum(arr[i-1][j-1:j+2] + [arr[i][j]] + arr[i+1][j-1:j+2]) for j in range(1, 5) for i in range(1, 5)]))
mathurk29 As array indices also start from zero, it would be convenient to let range function start from 0 (which it does by default):
print(max([sum(arr[i][j:j+3] + [arr[i+1][j+1]] + arr[i+2][j:j+3]) for i in range(4) for j in range(4)]))
askz6 Why does the max function contain brackets that also wrap around everything inside?
serious_nick it's a list comprehension https://python-course.eu/list_comprehension.php
meysam81 Excellent Well done
donggangcj print(max(sum(arr[i-1][j-1:j+2] + [arr[i][j]] + arr[i+1][j-1:j+2]) for j in range(1, 5) for i in range(1, 5))) no '[]' list generator,more faster!
alphasingh My Attempt :)
A = [] S = [] [A.append(list(map(int, input().split()))) for i in range(6)] [S.append(sum(A[i][j:j+3]+A[i+2][j:j+3])+A[i+1][j+1]) for i in range(4) for j in range(4)] print(max(S))
vivek0079 awesome and cool:)
CruiseDevice Python help me understand such questions easily
divyammehta Even I thought of the same solution but it doesnt pass a lot of test cases
rishravi To save space, you can check for max sum with every calculation of the hourglass sum. So instead of having an array with all values and then comparing the max, we can get the result as we traverse :)
alex_k_stamatis Nice simple solution! I feel stupid that I solved it with a 4D array now...
geekidharsh prefect pythonian solution
nitinkanagaraj Why is range(len(arr)-2) ?
dan_dinu A similar NodeJS solution:
var sum = []; for (i = 0; i < arr.length - 2; i++) { for (j =0; j < arr.length - 2; j++) { sum.push(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]); } } console.log(Math.max(...sum));
DavisOkoth Oh, cool. I did something similar but forgot Math.max(). I had to do a sort then get the final element in the array. Thanks!
vermashivani801 amazing !
vasilij_kolomie1 my approch has -1 calculation on each glass and no additional array sum. Look on it. . '''
def hourglassSum(arr):
len_arr = len(arr)
n=(len_arr-2)**2
s_max = None
for k in range(n):
i = k//(len_arr-2)
j = k%(len_arr-2)
if j==0: # new row glass sum
_ = sum((arr[i][0],arr[i][1],arr[i][2],
arr[i+1][1],
arr[i+2][0],arr[i+2][1],arr[i+2][2])
if(s_max is None):
s_max = _
else: # next glass in the same row sum calc
_ += (-arr[i][j-1]-arr[i+1][j]-arr[i+2][j-1] + \
arr[i][j+2]+arr[i+1][j+1]+arr[i+2][j+2])
s_max = max(s_max,_)
return s_max
'''
tony_cottam I think where most people are having problems (and where I was having problems) is that the array is being read in and then processed on opposite coordinates ( e.g. read in as (x, y) but then process as (y, x) ).
I decided this was the problem for me after I read in the array as a 1D array and then was able to solve no problem.
darnesmeister thanks man, didn't realize this without your hint
jlipata This is true. I tried outputting the matrix to the screen in standard x,y format, it does not look like the input. This caused a lot of confusion and time wasted while debugging. IMO, Hackerrank should fix this.
carolinebholmes I consider it a good lesson in paying attention to existing code (I fell prey to this problem as well)
andrewseaman35 It doesn't help that the initial test case passes when the indexing is switched.
debashishmitra That was the thing. Misleading pre provided scanning code. It scans by columns - not by rows - which I assume most would not expect. I was so sure mine was right but had no idea why certain test cases were failing. Only thing I had to change was to switch the for statements (outer to inner and inner to outer) and all test cases passed.
Yours is the most observant and helpful comment. Thanks much
arvind002 thanks bro, you saved my day!!
milad How the heck is this problem ranked as easy? Am I missing something or do people jus tlook at the solutions after 1 glance at the problem?
vaddi_party they are easy compared to the hard level problems. :)
snaran I agree with milad. This one was harder than https://www.hackerrank.com/challenges/sparse-arrays?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=3-day-campaign.
To make matter more complicated, I solved it by calculating the new hourglass value by subtracting out the old cells and adding the new cells, and made the hourglass size (3x3) configurable, and the array size configurable too. But even without this, it is harder than the one mentioned above.
techniker True the question isn't easy.
MoBotan I am guessing because you just have to brute force the solution. There is no smart/advanced way to get the answer.
jhall1468 A Javascript solution using
O(n*m)time complexity andO(1)space complexity.function hourGlass(arr) { // we could set this to 3 given the problems constraings, but this allows changes maxX = 3; // + (arr[0].length % 3) maxY = 3; // + (arr.length % 3) total = -Infinity; // has to be -64, but // begin at y == 0 for (let y = 0; y <= maxY; y++) { for (let x = 0; x <= maxX; x++) { // sum the top of hourglass let sum = arr[y][x] + arr[y][x+1] + arr[y][x+2]; // get the middle of hourglass sum += arr[y+1][x+1]; // sum the bottom of hourglass sum += arr[y+2][x] + arr[y+2][x+1] + arr[y+2][x+2] // don't store result to keep space complexity down if (total < sum) total = sum; } } return total; }
chadwalt Hey awesome solution, just a quick question why use -Infinity
MoBotan You can't set the initial value of 'total' to 0, because the answer might be lower. To avoid that, set the initial value to the lowest possible (-infinity).
The smallest number allowable for any of the numbers in the hourglass is -9. If all the numbers in an hourglass are -9, the lowest possible value for an hourglass is -63. So an initial value of -63 is ok too.
gacevic_danilo you can also use -64 since the lowest possible value is -63 :)
sairishab24 take a bow ..salute to ur code
manoranjan03 My Solution
public class Solution { public static void main(String[] args) {
Scanner sc = new Scanner(System.in); int[][] a = new int[6][6]; for(int i =0; i<6; i++){ for(int j=0; j<6; j++){ a[i][j] = sc.nextInt(); } } int sum =Integer.MIN_VALUE; for(int i =0; i<4; i++){ for(int j=0; j<4; j++){ int temp = a[i][j] + a[i][j+1] +a[i][j+2] +a[i+1][j+1] +a[i+2][j] +a[i+2][j+1] + a[i+2][j+2]; if(temp>sum){ sum = temp; } } } System.out.println(sum); /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ }}
keari Hi, maybe I am confused by what constitutes an hourglass...but wouldn't 15 be the largest hourglass sum for this test case? However the expected output is 13.
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 9 2 -4 -4 0
0 0 0 -2 0 0
0 0 -1 -2 -4 0
kravvcu the hourglass you bolded out is 1 + 1 + 9 + 2 = 13 you do not add the two outer 1's in the middle line with the three 1's above the line with 9
hoanganh17b [deleted]
ravi49167 yeah same here.
hoanganh17b [deleted]
tomade Rather simple and concise in Python 3:
#!/bin/python3 def hoursum(arr, r, c): return sum(arr[r - 1][c-1:c+2]) + arr[r][c] + sum(arr[r + 1][c-1:c+2]) arr = [[int(x) for x in input().split()] for _ in range(6)] ans = max(hoursum(arr, r, c) for r in range(1,5) for c in range(1,5)) print(ans)
will_deyl Did the same thing essentially. Just shortened it.
arr = [[int(x) for x in input().split()] for _ in range(6)] hoursum = lambda arr,r,c: sum(arr[r-1][c-1:c+2]) + arr[r][c] + sum(arr[r+1][c-1:c+2]) ans = max(hoursum(arr,r,c) for r in range(1,5) for c in range(1,5)) print(ans)
rmilejcz Wow this is amazing, I had like 50 lines of code. Thank you for this example, it is really helpful. I couldn't figure out how to make the range function work for me here but this makes SO much sense
alextab93 [deleted]
swisan My attempt, annotated for complete beginners to understand:
public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int matrix[][] = new int[6][6]; //Read in: for (int i = 0; i < 6; i++){ for (int j = 0; j < 6; j++) { matrix[i][j] = in.nextInt(); } } int maxSum = -64; //Because the minimum it could be is -9*7 = -63 int startCol = 0; //Each iteration of the outer loop is one hour glass: for (int row = 0; row <= 3; row++){ int sum = 0; //Initialize this specific hourglass' sum for (int col = startCol; col < startCol + 3; col ++) { sum += matrix[row][col]; //Gets current index that col and row are on if (col == startCol) { //Only doing it if it's on the startCol ensures we only add middle piece once sum += matrix[row+1][startCol+1]; } sum += matrix[row+2][col]; //Gets the corresponding index in the bottom row } startCol = (startCol < 3) ? startCol + 1 : 0; // If there is space for another hourglass in this row, goto // the next Col if (startCol != 0) { //If there is space for another hourglass in this row, continue in the same row row--; //You need to decrement in order to do this bc for loop will increment } if (sum > maxSum) { maxSum = sum; } //keeps track of what the maximum sum is so we can print it at the end } System.out.println(maxSum); } }
elenalizina90 My solution is:
int maxSum = (-9) * 7; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { int tmp = arr[i + 1][j + 1]; for (int k = 0; k < 3; k++) { tmp += arr[i][j + k] + arr[i + 2][j + k]; } if (tmp >= maxSum) maxSum = tmp; } } cout << maxSum;
Sort 919 Discussions, By:
Please Login in order to post a comment