The biggest product is two smallest negatives and one biggest positive.
The biggest product is negative itself(!), which can happen in at least these two distinct cases:
[n,p,p]: There are only 3 inputs, one of them negative. For any length 3 input we should just return the input anyway, implicitly or explicitly.
[n,n,n...]: There are 3 or more inputs, none of which are positive. In this case we should return the 3 negative numbers closest to 0 (3 biggest numbers, same as the all-positive happy case)
importmathdefget_product_of_3(array_of_ints):iflen(array_of_ints)<3:return0min_max=-math.infmin_max_i=0maxes=[min_max,min_max,min_max]max_neg=0max_neg_i=0negs=[0,0]forintinarray_of_ints:ifint>min_max:maxes[min_max_i]=intmin_max_i,min_max=min(enumerate(maxes),key=lambdax:x[1])ifint<max_neg:negs[max_neg_i]=intmax_neg_i,max_neg=max(enumerate(negs),key=lambdax:x[1])prod_maxes=maxes[0]*maxes[1]*maxes[2]prod_negs=negs[0]*negs[1]# This condition is only needed for `[n,p,p]`, to not return the invalid product of `0` when the product of maxes is negative.
ifprod_negs!=0:returnmax(prod_negs*max(maxes),prod_maxes)returnprod_maxes
If we instead explicitly return the product of 3 inputs, this condition is no longer needed:
Another possible optimization, for input such as [...-100,-99,-98,-97,1,-96,-95,-94...] is to stop expecting the "all negatives" case. This can easily be done by resetting all negative maxes to 0, so that incoming negatives are always smaller:
Ended up doing this by checking if the product of current number with the previous stored two numbers is greater than the the current max.
Had to store 5 variables:
Highest number
Lowest number
Highest product of two numbers.
Lowest product of two numbers.
Max product of previous 3 numbers.
Then with each new number I check if the max product is greater than previous, and also update each. As there are negative numbers, the lowest product of two numbers can suddenly give the max product when multiplied with the current.
This is O[n] which is still better than sort which is O[nlogn]
This was the logic:
Examples:
[10, 7, 5, 8, 11, 9] -> 990 ;
[10, 7, 100] -> 7000 ;
[-10, 7, 100] -> -7000;
[-10, 7, 100, 1] -> 700;
Github
I feel like much less comparisons can be done by keeping track of the lowest number:
Sorry, I replaced one language I don't know with a similar language I don't know because I didn't want to install ruby.
Thanks Mihail. This looks much more neat. Will test it out later.
But did you test the case if two negative numbers are passed?
For e.g [-5, -4, 1, 3, 2] -> should give 60.
Yes, I see the problem.
So far I see three cases:
[n,p,p]
: There are only 3 inputs, one of them negative. For any length 3 input we should just return the input anyway, implicitly or explicitly.[n,n,n...]
: There are 3 or more inputs, none of which are positive. In this case we should return the 3 negative numbers closest to 0 (3 biggest numbers, same as the all-positive happy case)I'll post a fix later, let's see how messy.
Okay, I think I got it:
If we instead explicitly return the product of 3 inputs, this condition is no longer needed:
Another possible optimization, for input such as
[...-100,-99,-98,-97,1,-96,-95,-94...]
is to stop expecting the "all negatives" case. This can easily be done by resetting all negative maxes to 0, so that incoming negatives are always smaller:Just realised that my original attempt was wrong !
For two negative integers e.g [-5, -4, 1, 3, 2] the correct answer is 60.
But the code above gives 6.
So.. need to change.
Ended up doing this by checking if the product of current number with the previous stored two numbers is greater than the the current max.
Had to store 5 variables:
Then with each new number I check if the max product is greater than previous, and also update each. As there are negative numbers, the lowest product of two numbers can suddenly give the max product when multiplied with the current.
This is O[n] which is still better than sort which is O[nlogn]
Will you believe me if I tell you that I didn't see this comment thread until now (well after posting my fixed solution)?
Ofcourse :) Only then would you have tried solving it twice and with a different logic.