Find Minimum Product among all Combinations of Triplets in an Array

Given an array of integers, find minimum product among all combinations of triplets in the array.


 

For example,


Input: { 4, -1, 3, 5, 9 }
Output: The minimum product is -45 (-1, 5, 9)

Input: { 1, 4, 10, -2, 4 }
Output: The minimum product is -80 (10, 4, -2)

Input: { 3, 4, 1, 2, 5 }
Output: The minimum product is 6 (3, 1, 2)

 
Naive solution would be to consider every combinations of triplets present in the array and calculate their product. The idea is to maintain the maximum product found so far in a variable and update it if the product of current triplet is greater. Its implementation can be seen here and runs in O(n3) time.

 

A better approach that takes O(nlogn) time is to sort the array. After the array is sorted, we simply return the minimum among product of its first three elements and the product of first element with its last two elements. This works as multiplication of two negative numbers results in a positive number and multiplication of a large positive number with a negative number results in a large negative number.

C++

Download   Run Code

Output:

The minimum product is -45

Java

Download   Run Code

Output:

The minimum product is -45

 

Linear time solution:

 
The following approach runs in O(n) time but takes O(n) extra space. The idea is to take help of four auxiliary arrays left_min[], left_max[], right_min[] and right_max[] of same size as the input array, where

  • left_min[i] contains minimum element to the left of A[i]
  • left_max[i] contains maximum element to the left of A[i]
  • right_min[i] contains minimum element to the right of A[i]
  • right_max[i] contains maximum element to the right of A[i]

Now after the arrays are constructed, we can get minimum and maximum element in left or right side for any element in the array in constant time. So we consider every element in the array as the middle element of the triplet, except the first and last element, and find the minimum by considering all possible combinations.

C

Download   Run Code

Output:

The minimum product is -45

Java

Download   Run Code

Output:

The minimum product is -45

 

Linear time and Constant space solution:

We have seen that the sorting solution only uses the first three and last two elements of the array, but sorts the whole array which modifies the input array and is also costly for large inputs. We can avoid that by finding the smallest, second smallest, third smallest element, largest and the second largest element in the array in linear time. Then like the sorting solution, we return the minimum among the product of smallest, second smallest, third smallest element of the array and the product of smallest element, largest element, second largest element of the array.

C

Download   Run Code

Output:

The minimum product is -45

Java

Download   Run Code

Output:

The minimum product is -45

 
Follow up: Print a triplet having maximum product in a given 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

avatar
  Subscribe  
Notify of