CareerCup

We only need 3 Max positive values and 2 Min neg values. This can be done in 5 passes at most (we can piggy pos and neg and reduce it to 3 passes). Then we only check whether P1P2P3 or P1N1N2 is greater.

This is a dupe. Please search the first 2-3 pages of this site and you will find it. Once you do, please click the Report Dup link.

We shouldn't be answering in terms of +ve or -ve numbers as there can be cases where all the numbers are either positive or negative. Just find the largest three and the smallest two and then check for which product is bigger. In this case the interviewer may be looking for the most optimum way to find those numbers.

This question definitely needs (2 -ve with 1 +ve) or (3 +ve) numbers.
Lets take the help of data structures to solve this
consider 3 heaps say H1,H2,H3
H1 -> max heap of negative numbers of size 3
H2 -> min heap of negative numbers of size 2
H3 -> max heap of positive numbers of size 3

Iterate through the array of integers and push the integers into their respective heaps (Push 0 in H1 if it comes)
Now H1 and H2 contain our primary results
if (H3 is empty) or (H3 has 2 entries) then take needed values in H1 (This explains all negative values case)
In all the other cases evaluate the required result accordingly

Please note that whatever the value of 'n' is the lookup is finally broken down to 8 numbers at-max

Complexity: It is only one run through the array. so it is O(n)

Note: The heaps solution is proposed as it will be easy to explain and the same can be used for higher problems also (say find 7 integers to find largest product where coding in terms of variables may be difficult)

Your heap solution seems to be good. Can you provide working code?

How about developing a hash table and find the smallest and largest numbers using hash functions. Using this, we can also reduce the time complexity from O(n) to O(1).

If it is only [min1,min2 and max3,max2,max1] is what you find, you can do this O(n) in single linear visit of the array. You'll need to spend constant time at each element doing a bunch of comparisons. Why would you want to maintain one or more heaps for this ?

I can see many alogs above with +ve and -ve number consideration.. but what if all numbers are -ve?

guys.. let it be -ve or +ve numbers..
we need to always find the max1,max2,max3 and min1 and min2
and check whether product of max1,2,3 is greater or min1,min2,max1 is greater..
now regarding DS..
v can keep hash but they have not mentioned anything about range of numbers..
so i feel .. 5 variables or normal linked list will solve the problem..
and no.of comparisons can be easily reduced...
pls correct me if i am wrong..

you can keep 5 variable: max1,max2,max3,min1,min2 and you can fill them by 5 comparisons at each step in a single pass (O(n))

Why are we looking for max1,min1,min2 (max1 is max no in +ve nos and min1,min2 are two lowest numbers in -ve numbers) for the case of negative number inclusion.
Is not it should be a,b,c where a = max no in +ve numbers and b,c are two max -ve numbers.

Please clarify.