# 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.

## Java

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

## Java

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.

## Java

Output:

Pair is (-10, -3)

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

Subscribe
Notify of
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.

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.