In array (vector) of numbers find two numbers, product of which is the biggest. Using nested loops is forbiden

Question

I have vector array.
user inputs some integer values in it.
For instance vector array can be like this:
array = [1, 2, 3, 4, 5, 333, 123, 534, 1, 3, 0, -12, -11]
How to find pair of numbers in this vector the product of which is the biggest? Do not use nested loops (loop in loop), it is forbidden. I don't need ready solution, i need just an idea. Thank you so much 😉

Answer 1

The best idea that comes to mind is to find the 2 largest positive and the 2 smallest negative numbers. One of those pairs has the largest product in the array.

This can be done in linear time and with just one pass. Have 2 variables largest and second_largest and initialize them to the smallest possible value. As you iterate over the array check whether the value is greater than largest. If so, put largest in second_largest and update largest to the new value. If the value is not greater than largest but greater than second_largest, update second_largest.

This same idea can be implemented for the 2 smallest negative values too.

At the end take whichever pair produces the largest product.

There is one edges that you need to take care of: The array has only 2 values and they have different signs or one of them is zero. Take care of this edge case by checking the array length and if it is 2, just return the product of those 2 values as you cannot do any better. This edge case can also be taken care of in the main algorithm, as pointed out by @apple-apple, but I wanted to make sure you are consciously aware of it.