Find maximum product of two integers in an array

Given an array of integers, find maximum product of two integers in an array.

 

For example, consider array {-10, -3, 5, 6, -2}

Maximum product is formed by (-10, -3) or (5, 6) pair.

 


 

Naive solution would be to consider every pair of elements and calculate their product. We update maximum product found so far if the product of current pair is greater. Finally, we print the elements involved in maximum product.

C++

Download   Run Code

Java

Download   Run Code



Output:

Pair is (-10, -3)

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1).
 


 

Time complexity can be improved by sorting the array. Then the maximum product is formed by maximum of

  • product of maximum and second maximum integer in the array which are last two elements in sorted array.
  • product of minimum and second minimum integer in the array which are first two elements in sorted array

C++

Download   Run Code

Java

Download   Run Code



Output:

Pair is (-10, -3)

 
The time complexity of above solution is O(nlogn) and auxiliary space used by the program is O(1).
 


 
We can solve this problem in linear time as we need only maximum, second maximum, minimum and second minimum element to solve this problem. We can compute all these in only single traversal of the array which accounts for O(n) time complexity.

C++

Download   Run Code

Java

Download   Run Code



Output:

Pair is (-10, -3)

Exercise: Find maximum product of three integers in an array

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
abdullah farwees
abdullah farwees

Guys , You ppl are doing a great job…!!!

I think , We can still optimize the last solution just using single traversal to find min1, min2 ,max1 and max2 using “single loop” which is also account for O(N) time complexity.This plays a major role when array contains billions/trillions of elements.

http://ideone.com/jTjN7R
Traverse an array once instead two times.

Keep rocking….Happy Coding.

wpDiscuz