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 the array {-10, -3, 5, 6, -2}. The maximum product is formed by the (-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

  1. product of maximum and second maximum integer in the array which are last two elements in sorted array.
     
  2. 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, -20)

 
The time complexity of above solution is O(nlog(n)) 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 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
abdullah farwees
Guest
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.

Stithi
Guest
Stithi

Hi, I’m new in programming. I think, your logic wont work if the array contains duplicates.
Example : {-3,8,10,-10, 20,0,25,25,-8 }; Expected out put : 625. your logic will return 500.
Though brute force and sorting methods work.