Find a Triplet having Maximum Product in an Array

Given an array of integers, find a triplet having maximum product in the array.


 

For example,


Input: { -4, 1, -8, 9, 6 }
Output: The Triplet having maximum product is (-4, -8, 9)

Input: { 1, 7, 2, -2, 5 }
Output: The Triplet having maximum product is (7, 2, 5)

 

Brute-force solution would be to consider every triplet present in the array and compute product of its elements. Finally after processing all triplets, we print the triplet having the maximum product. The time complexity of this solution would be O(n3).

 
A better approach involves sorting the array. Then the triplet having maximum product can be one of the two:

  1. The last three elements of the sorted array.
     
  2. First two element and the last element of the sorted array (as multiplication of two negative numbers results in a positive number).

 
C++ implementation –

 

Download   Run Code

Output:

Triplet is (-8, -4, 9)

 
The time complexity of above solution is O(nlogn) which is better than the brute force solution but is still costly for a large input. The solution also modifies the input array, which might not be permitted.

 

Can we do better?

If we carefully analyze the above solution, we can see that it only uses the last three and first two elements of the sorted array. We can avoid that by finding the largest, second largest, third largest element, and the smallest, second smallest element in the array in linear time as shown in below solution.

 
C implementation –

 

Download   Run Code

Output:

Triplet is (-8, -4, 9)

 

 
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
wpDiscuz