We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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. :)
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).
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 .
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!
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!
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
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 :)
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.
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
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.
Because of the -9<= A[i][j] <=9, so the extrame situation is that all the 7 elem are -9, the sum is -63, and any value that smaller than -63 could be set to the initial value.
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
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!
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
Actually, since the constraint is -9, and you are adding 7 values, the minimum would be -9 x 7 which is -63. That could save a fraction of memory instead of working with a large negative number.
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.
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.
jj=(jj<3)?jj+1:0;// set 0 if jj(collumn pointer) set in one position which allows calculate an hourglassif(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
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.
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
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.
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.
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];
}
}
}
}
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!
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
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.
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.
I set the value to None (Python 3) and set the max_value the first time it is calculated. Others have suggested that setting the value to -63 (7 * -9) is sufficient, which it is, but what happens when the spec changes (real world) and now we need to reset the initial max_value to whatever the lowest possible value could be.
integer.MIN_VALUE works as well. Generally I am against 'magic numbers' so None or the absolute lowest known value make the solution more scalable IMHO.
Coming from C++ I guess the question is does the underlying implementation when sent to a exe maker such as py2exe or when interpretted take into account things like memory allocation etc. While in this case storing all values is trivial what about in cases where hte list could potentially be thousands of items long. Even with the use of iterables we're talking about a memory. I assume you could say the comparison can either be done in loop or @ the end as this code does.
2D Array - DS
You are viewing a single comment's thread. Return to all comments →
if you want to pass test Case 3 and 5 dont initialize max value to 0.
yeah. you should initialize the max value to the value of the first hourglass.
you can also set any large negative value also. Then no need to caluculate first hourglass separately.
for e.g , max_value = -99999;
This is helpful, thank you. I used Integer.MIN_VALUE;
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. :)
I think the input variables are defined as primitive type int.
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;
}
will it not give a compilation error i.e max is not initialized or something like that?
Using your logic, you could use the type byte.
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).
max negative value is -63 (-9 * 7)
anything less than -54.
For python initialize with: -9223372036854775807
It passed the testcases but why it doesn't runs when initialized to zero?
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 .
thanks mate... helped a lot!!!
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!
Actually, -63 will work too.
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!
Taking max value as integer.MIN_VALUE is also correct however max can also be sumArray[0] (the array of sum of hourglasses) .
Thanks ! That helped.
Zero is considered to be a positive number. If all the hour glasse's totals are negative they wont beat your zero.
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
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 :)
Yes. In case the constraints are not there, use Integer.MIN_VALUE.
yes it worked. thanks
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.
I just did this:
you can initilize to arrays first value, that is at a[0]
This is wrong - because you sum 7 numbers, which all can be -9. a[0] can be -9, but the minimal value can be -63
Simply set it to null and use type specific comparison to assign first sum.
why do we need to set max to -63 or to any such value ?
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.
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
why should we initialize max value to large negative value?
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.
what is the hour glass
Because of the -9<= A[i][j] <=9, so the extrame situation is that all the 7 elem are -9, the sum is -63, and any value that smaller than -63 could be set to the initial value.
thanks for the help..
The least no. possible is -9 * 7 = -63. We can also initialize it to that. :)
Thanks
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
I used Number.NEGATIVE_INFINITY with Javascript
you can set it to integer.MIN_VALUE
You can use -63 as max value because it is stated in condition that a[i][j] is between -9 and + 9
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
may i know what is the reason behind this? why we have to initiliza ma_value = -9999 or -63
since the hourglass with smallest sum is -63 when all values in hourglass are -9
-63 would be enough
bro you can just set max value to -9 * 7 = -63 cause it can be the most small value of hourglass acording to question
even -63 can work fine
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.
perhaps -9*7 is enough, though
you could just use one less than the minimum possible value of an hourglass, which is -64.
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!
since the least sum is -63 (when all elements are -9), you can initialize it to be -63
Or you can use
which gives you the largest negative value.
Worked like a charm. Thanks. I didnt know we can compare floats and integers.
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
short mayor=-63;
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.
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
Actually, since the constraint is -9, and you are adding 7 values, the minimum would be -9 x 7 which is -63. That could save a fraction of memory instead of working with a large negative number.
This was helpful, thanks a ton.
Great solution if you don't care about scalability or the assumption that the dataset changes over time. Terrible solution if you do.
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.
how to do this task in C???
sorry, i am not familiar with c language.
why have u assigned maxsum=-1000 ? can u elobarate
the inputs also given in negitive....
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.
why did you use j=jj
what the below statement does in the code?
if(jj != 0) i--;
To run loop for same value of i with different values for j untill j maximum limit is reached
why not take -1
could anyone identify the mistake
in for loop try i<4 instead of i<3
Whats the reason behind i<4..Not able to get the reason.Can you explain please
there are 4 hourglasses vertically and 4 hourglasses horizontally
I didnt understand this part. Can somebody help me out in this?
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.
This code passes all the test cases
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())<
-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
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.
Hi, you're including a bunch of extraneous libraries. You are just using vector, iostream, and algorithm.
The rest could be deleted :) Cheers
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"<
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
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"<
how to add back ticks? i am unable to add the pdf file as well plzz help.
:O Are you using all those includes?
Simple and efficient and also easy to understand . Thank you sir.
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.
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]); } }
}
Holy for-loops, Batman
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]; } } } }
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!
Thanks
I did it in Python 3 and I initialized it as None, and put an if condition to check if result_max is none or not
if we dont know the input then there is no chance of getting hourglass
Utilizing the None, nil, or null the abscense of a value is useful for preventing issues like this.
You can also intialize max value to -Infinity. In Python, you can do that by -float('inf')
yeah you can init max value to one less than the least value possible, in this case its '-55'
least value of sum possible = -9*7 = -63 so init max = -64
thanks for the correction mandar012 and my apologies for posting such wrong ans
Why not just use
max = -63? If the whole array is-9then max will never change and output correct answer of-63You're right, that's the best initial value.
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
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.
that's a good idea! whenever you can decrease the number of possible causes of a problem, that's a good thing!
-64
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
You can actually set -9, which is given in problem statement. :)
Yeah I wonder what percentage of people (me included) wrote everything correct the first attempt, but initialized at 0 ;)
i have 1 idea for that. first find min value from max=0arr[j][i]
Why is that? I dont understand the logic in it.
i intiliza max value -999 iam getting error can u have a c code
Good catch!!
I used
In python 3 I have used, MIN = -sys.maxsize -1
yes, you should not intialize maximum to zero its better to intialize with a large negative number
why am i getting timeout? my complexity is O(n^2)(for finding max)and for computing hourglass sum itts O(n)
Not just better, mandatory; initializing to zero is wrong.
thank you
initialise to a negative number
or just test for and initialise the total to the first hourglass value
i initialised max value with -63. it worked
Just intialize max value to -63.
For Python 3, the minimum value an integer can have is:
then what should be taken
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.
//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<
Initialize max_value = -63, as the minimun value of an hourglass can be only -63. No need to assign large negative value as -99999.
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);
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
lol I made this mistake the first time too.
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.
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.
Too late lost 5 hackos......
And now I feel dumb for not thinking of this issue earlier.
Instead we can initialize max value to -64 as the max negative we can obtain is 7*-9
I set the value to None (Python 3) and set the max_value the first time it is calculated. Others have suggested that setting the value to -63 (7 * -9) is sufficient, which it is, but what happens when the spec changes (real world) and now we need to reset the initial max_value to whatever the lowest possible value could be.
integer.MIN_VALUE works as well. Generally I am against 'magic numbers' so None or the absolute lowest known value make the solution more scalable IMHO.
Cool, thanks for the feedback!
pattern is everything (for pythoholics)
Coming from C++ I guess the question is does the underlying implementation when sent to a exe maker such as py2exe or when interpretted take into account things like memory allocation etc. While in this case storing all values is trivial what about in cases where hte list could potentially be thousands of items long. Even with the use of iterables we're talking about a memory. I assume you could say the comparison can either be done in loop or @ the end as this code does.