Find minimum product among all combinations of triplets in an array

P roblem

Find the minimum product of any three triplets in an array.

Sample Input

[1, 2, 3, 4]

Sample Output

6

Approach

We can sort the array and find the minimum product of the first 3 numbers and the product of the last two numbers and the first number. This is because a large number multiplied by a negative number will give a large negative number. This approach takes O(NlogN) time.

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
intsolve(vector<int> arr) 
{
 sort(arr.begin(), arr.end());
 int n = arr.size();
 return min(arr[n-1] * arr[n-2] * arr[0], arr[0] * arr[1] * arr[2]);
}
intmain()
{
 vector<int> arr = { 2, -1, 3, -5, 1 };
 int min = solve(arr);
 cout << "Minimum product is " << min;
}

Output

Minimum product is -30

Java

import java.util.Arrays;
classMain
{
 publicstaticintsolve(int[] arr)
 {
 int n = arr.length;
 
 Arrays.sort(arr);
 return Integer.min(arr[n-1] * arr[n-2] * arr[0], arr[0] * arr[1] * arr[2]);
 }
 publicstaticvoidmain(String[] args)
 {
 int[] arr = { 1, -1, 3, 5, 10 };
 int min = solve(arr);
 System.out.print("Minimum product is " + min);
 }
}

Output

Minimum product is -50

Python

def solve(arr):
 n = len(arr)
 arr.sort()
 return min(arr[n-1] * arr[n-2] * arr[0], arr[0] * arr[1] * arr[2])
arr = [1, -1, 2, 9]
min = solve(arr)
print("Minimum product is", min)

Output

Minimum product is -18

People are also reading:

• Left Rotate an Array
• Sorted Triplet in an Array
• Shift All Matrix Elements by 1 in Spiral Order
• Print Matrix in Spiral Form
• Job Sequencing Problem
• Activity Selection Problem
• Find Subarrays within Given Sum in an Array
• Find MSB in O(1)
• Count subarrays with given XOR
• Find MSB