How to find Minimum product triplet in an array?

Question: Given an integer array, find a minimum product of a triplet in array.

Sample Input:

5

4 -1 3 5 9

ANSWER: -45 (-1,9,5)

The first line of input contains N the number of integers in an array. The second line contains N integers.

We must print the minimum product alone.

C Solution:

#include <stdlib.h>
#include <stdio.h>
#define MIN(a,b) ((a<b)?a:b)
int cmp(const void *x,const void *y){
    return *(int*)x - *(int*)y;
}
int main()
{
    int N;
    scanf("%d",&N);
    int array[N];
    for(int i=0;i<N;i++)
        scanf("%d",&array[i]);
    qsort(array,N,sizeof(int),cmp);
    if(array[0]<0){
        printf("%d",MIN(array[0]*array[1]*array[2],array[0]*array[N-2]*array[N-1]));
    }
    else{
        printf("%d",array[0]*array[1]*array[2]);
    }
    return 0;
}

Python Solution:

n = int(input())
l = list(map(int,input().split()))
l.sort()
if(l[0]<0): print(min(l[1]*l[0]*l[2],l[0]*l[n-1]*l[n-2]))
else: print(l[0]*l[1]*l[2])

In both the above languages we have implemented same algorithm, we sort the array to minimize the complexity for finding the triplet.

In C qsort is a builtin function available in stdlib.h header file which sorts 1 Million integers is 0.247883 sec so its much efficient than standard sorting algorithms.

In Python sort function’s time complexity is O(n log n) which is better.

After sorting the elements we have only three possibility of minimum product triplet, which is separated using if else condition. So its simple how large may be the array we can find the triplet easily.