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

(2 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

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

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 output : 625. your logic will return 500.
Though brute force and sorting methods work.

Guest

why do we need to check if the arr[i] is greater than max2? Even if we don’t, at the end max2 is bound to have the second largest because everytime we find an element greater than max1, we store max1 in max2. So by induction, when we reach the end of the array max2 should be the second largest