Maximum product of a triplet (subsequence of size 3) in array
Given an integer array, find a maximum product of a triplet in the array.
Examples:
Input: [10, 3, 5, 6, 20]
Output: 1200
Explanation: Multiplication of 10, 6 and 20Input: [-10, -3, -5, -6, -20]
Output: -90Input: [1, -4, 3, -6, 7, 0]
Output: 168
Naive Approach:
A simple solution is to check for every triplet using three nested loops. Below is its implementation :
// A C++ program to find a maximum product of a
// triplet in array of integers
#include <bits/stdc++.h>
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// will contain max product
int max_product = INT_MIN;
for (int i = 0; i < n - 2; i++)
for (int j = i + 1; j < n - 1; j++)
for (int k = j + 1; k < n; k++)
max_product = max(max_product,
arr[i] * arr[j] * arr[k]);
return max_product;
}
// Driver program to test above functions
int main()
{
int arr[] = { 10, 3, 5, 6, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout << "No Triplet Exists";
else
cout << "Maximum product is " << max;
return 0;
}
// A Java program to find a
// maximum product of a
// triplet in array of integers
class GFG {
// Function to find a maximum
// product of a triplet in array
// of integers of size n
static int maxProduct(int []arr, int n)
{
// if size is less than
// 3, no triplet exists
if (n < 3)
return -1;
// will contain max product
int max_product = Integer.MIN_VALUE;
for (int i = 0; i < n - 2; i++)
for (int j = i + 1; j < n - 1; j++)
for (int k = j + 1; k < n; k++)
max_product = Math.max(max_product,
arr[i] * arr[j] * arr[k]);
return max_product;
}
// Driver Code
public static void main (String [] args)
{
int []arr = { 10, 3, 5, 6, 20 };
int n = arr.length;;
int max = maxProduct(arr, n);
if (max == -1)
System.out.println("No Triplet Exists");
else
System.out.println("Maximum product is " + max);
}
}
# Python3 program to find a maximum
# product of a triplet in array
# of integers
import sys
# Function to find a maximum
# product of a triplet in array
# of integers of size n
def maxProduct(arr, n):
# if size is less than 3,
# no triplet exists
if n < 3:
return -1
# will contain max product
max_product = -(sys.maxsize - 1)
for i in range(0, n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
max_product = max(
max_product, arr[i]
* arr[j] * arr[k])
return max_product
# Driver Program
arr = [10, 3, 5, 6, 20]
n = len(arr)
max = maxProduct(arr, n)
if max == -1:
print("No Triplet Exits")
else:
print("Maximum product is", max)
# This code is contributed by Shrikant13
// A C# program to find a
// maximum product of a
// triplet in array of integers
using System;
class GFG {
// Function to find a maximum
// product of a triplet in array
// of integers of size n
static int maxProduct(int []arr, int n)
{
// if size is less than
// 3, no triplet exists
if (n < 3)
return -1;
// will contain max product
int max_product = int.MinValue;
for (int i = 0; i < n - 2; i++)
for (int j = i + 1; j < n - 1; j++)
for (int k = j + 1; k < n; k++)
max_product = Math.Max(max_product,
arr[i] * arr[j] * arr[k]);
return max_product;
}
// Driver Code
public static void Main ()
{
int []arr = { 10, 3, 5, 6, 20 };
int n = arr.Length;;
int max = maxProduct(arr, n);
if (max == -1)
Console.WriteLine("No Triplet Exists");
else
Console.WriteLine("Maximum product is " + max);
}
}
// This code is contributed by anuj_67.
<script>
// JavaScript program to find a
// maximum product of a
// triplet in array of integers
// Function to find a maximum
// product of a triplet in array
// of integers of size n
function maxProduct(arr, n)
{
// if size is less than
// 3, no triplet exists
if (n < 3)
return -1;
// will contain max product
let max_product = Number.MIN_VALUE;
for (let i = 0; i < n - 2; i++)
for (let j = i + 1; j < n - 1; j++)
for (let k = j + 1; k < n; k++)
max_product = Math.max(max_product,
arr[i] * arr[j] * arr[k]);
return max_product;
}
// Driver Code
let arr = [ 10, 3, 5, 6, 20 ];
let n = arr.length;;
let max = maxProduct(arr, n);
if (max == -1)
document.write("No Triplet Exists");
else
document.write("Maximum product is " + max);
</script>
<?php
// A PHP program to find a
// maximum product of a
// triplet in array of integers
// Function to find a maximum
// product of a triplet
// in array of integers of
// size n
function maxProduct($arr, $n)
{
$INT_MIN = 0;
// if size is less than
// 3, no triplet exists
if ($n < 3)
return -1;
// will contain max product
$max_product = $INT_MIN;
for ($i = 0; $i < $n - 2; $i++)
for ($j = $i + 1; $j < $n - 1; $j++)
for ($k = $j + 1; $k < $n; $k++)
$max_product = max($max_product,
$arr[$i] * $arr[$j] * $arr[$k]);
return $max_product;
}
// Driver Code
$arr = array(10, 3, 5, 6, 20 );
$n = sizeof($arr);
$max = maxProduct($arr, $n);
if ($max == -1)
echo "No Triplet Exists";
else
echo "Maximum product is " ,$max;
// This code is contributed by nitin mittal.
?>
Output
Maximum product is 1200
Time Complexity: O(n3)
Auxiliary Space: O(1)
Approach 2:
- Construct four auxiliary arrays leftMax[], rightMax[], leftMin[] and rightMin[] of same size as input array.
- Fill leftMax[], rightMax[], leftMin[] and rightMin[] in below manner.
- leftMax[i] will contain maximum element on left of arr[i] excluding arr[i]. For index 0, left will contain -1.
- leftMin[i] will contain minimum element on left of arr[i] excluding arr[i]. For index 0, left will contain -1.
- rightMax[i] will contain maximum element on right of arr[i] excluding arr[i]. For index n-1, right will contain -1.
- rightMin[i] will contain minimum element on right of arr[i] excluding arr[i]. For index n-1, right will contain -1.
- For all array indexes i except first and last index, compute maximum of arr[i]*x*y where x can be leftMax[i] or leftMin[i] and y can be rightMax[i] or rightMin[i].
- Return the maximum from step 3.
Below is the implementation of the above approach:
// A C++ program to find a maximum product of a triplet
// in array of integers
#include <bits/stdc++.h>
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
vector<int> leftMin(n, -1);
vector<int> rightMin(n, -1);
vector<int> leftMax(n, -1);
vector<int> rightMax(n, -1);
// will contain max product
int max_product = INT_MIN;
// to store maximum element on left of array
int max_sum = arr[0];
// to store minimum element on left of array
int min_sum = arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for (int i = 1; i < n; i++)
{
leftMax[i] = max_sum;
if (arr[i] > max_sum)
max_sum = arr[i];
leftMin[i] = min_sum;
if (arr[i] < min_sum)
min_sum = arr[i];
}
// reset max_sum to store maximum element on
// right of array
max_sum = arr[n - 1];
// reset min_sum to store minimum element on
// right of array
min_sum = arr[n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for (int j = n - 2; j >= 0; j--)
{
rightMax[j] = max_sum;
if (arr[j] > max_sum)
max_sum = arr[j];
rightMin[j] = min_sum;
if (arr[j] < min_sum)
min_sum = arr[j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for (int i = 1; i < n - 1; i++)
{
int max1 = max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i]);
int max2 = max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i]);
max_product = max(max_product, max(max1, max2));
}
return max_product;
}
// Driver program to test above functions
int main()
{
int arr[] = { 1, 4, 3, -6, -7, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout << "No Triplet Exists";
else
cout << "Maximum product is " << max;
return 0;
}
// A Java program to find a maximum product of a triplet
// in array of integers
import java.util.*;
class GFG
{
/* Function to find a maximum product of a triplet
in array of integers of size n */
static int maxProduct(int []arr, int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
int[] leftMin = new int[n];
int[] rightMin = new int[n];
int[] leftMax = new int[n];
int[] rightMax = new int[n];
Arrays.fill(leftMin, -1);
Arrays.fill(leftMax, -1);
Arrays.fill(rightMax, -1);
Arrays.fill(rightMin, -1);
// will contain max product
int max_product = Integer.MIN_VALUE;
// to store maximum element on left of array
int max_sum = arr[0];
// to store minimum element on left of array
int min_sum = arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for (int i = 1; i < n; i++)
{
leftMax[i] = max_sum;
if (arr[i] > max_sum)
max_sum = arr[i];
leftMin[i] = min_sum;
if (arr[i] < min_sum)
min_sum = arr[i];
}
// reset max_sum to store maximum element on
// right of array
max_sum = arr[n - 1];
// reset min_sum to store minimum element on
// right of array
min_sum = arr[n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for (int j = n - 2; j >= 0; j--)
{
rightMax[j] = max_sum;
if (arr[j] > max_sum)
max_sum = arr[j];
rightMin[j] = min_sum;
if (arr[j] < min_sum)
min_sum = arr[j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for (int i = 1; i < n - 1; i++)
{
int max1 = Math.max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i]);
int max2 = Math.max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i]);
max_product = Math.max(max_product, Math.max(max1, max2));
}
return max_product;
}
// Driver code
public static void main (String[] args)
{
int []arr = { 1, 4, 3, -6, -7, 0 };
int n = arr.length;
int max = maxProduct(arr, n);
if (max == -1)
System.out.println("No Triplet Exists");
else
System.out.println("Maximum product is "+max);
}
}
// This code is contributed by mits
# A Python3 program to find a maximum product
# of a triplet in array of integers
import sys
# Function to find a maximum product of a
# triplet in array of integers of size n
def maxProduct(arr, n):
# If size is less than 3, no triplet exists
if (n < 3):
return -1
# Construct four auxiliary vectors
# of size n and initialize them by -1
leftMin = [-1 for i in range(n)]
rightMin = [-1 for i in range(n)]
leftMax = [-1 for i in range(n)]
rightMax = [-1 for i in range(n)]
# Will contain max product
max_product = -sys.maxsize - 1
# To store maximum element on
# left of array
max_sum = arr[0]
# To store minimum element on
# left of array
min_sum = arr[0]
# leftMax[i] will contain max element
# on left of arr[i] excluding arr[i].
# leftMin[i] will contain min element
# on left of arr[i] excluding arr[i].
for i in range(1, n):
leftMax[i] = max_sum
if (arr[i] > max_sum):
max_sum = arr[i]
leftMin[i] = min_sum
if (arr[i] < min_sum):
min_sum = arr[i]
# Reset max_sum to store maximum
# element on right of array
max_sum = arr[n - 1]
# Reset min_sum to store minimum
# element on right of array
min_sum = arr[n - 1]
# rightMax[i] will contain max element
# on right of arr[i] excluding arr[i].
# rightMin[i] will contain min element
# on right of arr[i] excluding arr[i].
for j in range(n - 2, -1, -1):
rightMax[j] = max_sum
if (arr[j] > max_sum):
max_sum = arr[j]
rightMin[j] = min_sum
if (arr[j] < min_sum):
min_sum = arr[j]
# For all array indexes i except first and
# last, compute maximum of arr[i]*x*y where
# x can be leftMax[i] or leftMin[i] and
# y can be rightMax[i] or rightMin[i].
for i in range(1, n - 1):
max1 = max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i])
max2 = max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i])
max_product = max(max_product, max(max1, max2))
return max_product
# Driver code
arr = [ 1, 4, 3, -6, -7, 0 ]
n = len(arr)
Max = maxProduct(arr, n)
if (Max == -1):
print("No Triplet Exists")
else:
print("Maximum product is", Max)
# This code is contributed by rag2127
// A C# program to find a maximum product of a triplet
// in array of integers
using System;
class GFG
{
/* Function to find a maximum product of a triplet
in array of integers of size n */
static int maxProduct(int []arr, int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
int[] leftMin=new int[n];
int[] rightMin=new int[n];
int[] leftMax=new int[n];
int[] rightMax=new int[n];
Array.Fill(leftMin,-1);
Array.Fill(leftMax,-1);
Array.Fill(rightMax,-1);
Array.Fill(rightMin,-1);
// will contain max product
int max_product = int.MinValue;
// to store maximum element on left of array
int max_sum = arr[0];
// to store minimum element on left of array
int min_sum = arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for (int i = 1; i < n; i++)
{
leftMax[i] = max_sum;
if (arr[i] > max_sum)
max_sum = arr[i];
leftMin[i] = min_sum;
if (arr[i] < min_sum)
min_sum = arr[i];
}
// reset max_sum to store maximum element on
// right of array
max_sum = arr[n - 1];
// reset min_sum to store minimum element on
// right of array
min_sum = arr[n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for (int j = n - 2; j >= 0; j--)
{
rightMax[j] = max_sum;
if (arr[j] > max_sum)
max_sum = arr[j];
rightMin[j] = min_sum;
if (arr[j] < min_sum)
min_sum = arr[j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for (int i = 1; i < n - 1; i++)
{
int max1 = Math.Max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i]);
int max2 = Math.Max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i]);
max_product = Math.Max(max_product, Math.Max(max1, max2));
}
return max_product;
}
// Driver code
static void Main()
{
int []arr = { 1, 4, 3, -6, -7, 0 };
int n = arr.Length;
int max = maxProduct(arr, n);
if (max == -1)
Console.WriteLine("No Triplet Exists");
else
Console.WriteLine("Maximum product is "+max);
}
}
// This code is contributed by mits
<script>
// A javascript program to find a maximum product of a triplet
// in array of integers
/* Function to find a maximum product of a triplet
in array of integers of size n */
function maxProduct(arr , n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
leftMin = Array.from({length: n}, (_, i) => -1);
rightMin = Array.from({length: n}, (_, i) => -1);
leftMax = Array.from({length: n}, (_, i) => -1);
rightMax = Array.from({length: n}, (_, i) => -1);
// will contain max product
var max_product = Number.MIN_VALUE;
// to store maximum element on left of array
var max_sum = arr[0];
// to store minimum element on left of array
var min_sum = arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for (i = 1; i < n; i++)
{
leftMax[i] = max_sum;
if (arr[i] > max_sum)
max_sum = arr[i];
leftMin[i] = min_sum;
if (arr[i] < min_sum)
min_sum = arr[i];
}
// reset max_sum to store maximum element on
// right of array
max_sum = arr[n - 1];
// reset min_sum to store minimum element on
// right of array
min_sum = arr[n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for (j = n - 2; j >= 0; j--)
{
rightMax[j] = max_sum;
if (arr[j] > max_sum)
max_sum = arr[j];
rightMin[j] = min_sum;
if (arr[j] < min_sum)
min_sum = arr[j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for (i = 1; i < n - 1; i++)
{
var max1 = Math.max(arr[i] * leftMax[i] * rightMax[i],
arr[i] * leftMin[i] * rightMin[i]);
var max2 = Math.max(arr[i] * leftMax[i] * rightMin[i],
arr[i] * leftMin[i] * rightMax[i]);
max_product = Math.max(max_product, Math.max(max1, max2));
}
return max_product;
}
// Driver code
var arr = [ 1, 4, 3, -6, -7, 0 ];
var n = arr.length;
var max = maxProduct(arr, n);
if (max == -1)
document.write("No Triplet Exists");
else
document.write("Maximum product is "+max);
// This code is contributed by Amit Katiyar
</script>
<?php
// A PHP program to find a maximum product of a triplet
// in array of integers
/* Function to find a maximum product of a triplet
in array of integers of size n */
function maxProduct($arr, $n)
{
// if size is less than 3, no triplet exists
if ($n < 3)
return -1;
// Construct four auxiliary vectors
// of size n and initialize them by -1
$leftMin=array_fill(0,$n, -1);
$rightMin=array_fill(0,$n, -1);
$leftMax=array_fill(0,$n, -1);
$rightMax=array_fill(0,$n, -1);
// will contain max product
$max_product = PHP_INT_MIN;
// to store maximum element on left of array
$max_sum = $arr[0];
// to store minimum element on left of array
$min_sum = $arr[0];
// leftMax[i] will contain max element
// on left of arr[i] excluding arr[i].
// leftMin[i] will contain min element
// on left of arr[i] excluding arr[i].
for ($i = 1; $i < $n; $i++)
{
$leftMax[$i] = $max_sum;
if ($arr[$i] > $max_sum)
$max_sum = $arr[$i];
$leftMin[$i] = $min_sum;
if ($arr[$i] < $min_sum)
$min_sum = $arr[$i];
}
// reset max_sum to store maximum element on
// right of array
$max_sum = $arr[$n - 1];
// reset min_sum to store minimum element on
// right of array
$min_sum = $arr[$n - 1];
// rightMax[i] will contain max element
// on right of arr[i] excluding arr[i].
// rightMin[i] will contain min element
// on right of arr[i] excluding arr[i].
for ($j = $n - 2; $j >= 0; $j--)
{
$rightMax[$j] = $max_sum;
if ($arr[$j] > $max_sum)
$max_sum = $arr[$j];
$rightMin[$j] = $min_sum;
if ($arr[$j] < $min_sum)
$min_sum = $arr[$j];
}
// For all array indexes i except first and
// last, compute maximum of arr[i]*x*y where
// x can be leftMax[i] or leftMin[i] and
// y can be rightMax[i] or rightMin[i].
for ($i = 1; $i < $n - 1; $i++)
{
$max1 = max($arr[$i] * $leftMax[$i] * $rightMax[$i],
$arr[$i] * $leftMin[$i] * $rightMin[$i]);
$max2 = max($arr[$i] * $leftMax[$i] * $rightMin[$i],
$arr[$i] * $leftMin[$i] * $rightMax[$i]);
$max_product = max($max_product, max($max1, $max2));
}
return $max_product;
}
// Driver program to test above functions
$arr = array( 1, 4, 3, -6, -7, 0 );
$n = count($arr);
$max = maxProduct($arr, $n);
if ($max == -1)
echo "No Triplet Exists";
else
echo "Maximum product is ".$max;
// This code is contributed by mits
?>
Output
Maximum product is 168
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach 3: Using priority queues.
- Create two Priority Queues. The first one (pqmin) is of default order and the Second one (pqmax) is of reverse order.
- Iterate through the array and insert all elements in both priority queues.
- Initialize a variable maximum with the first element in pqmax and remove it from pqmax.
- Create two variables product1 and product2.
- product1= maximum*pqmax.poll()*pqmax.poll().
- product2= maximum*pqmin.poll()*pqmin.poll().
- return the greatest of product1 and product2.
Below is the implementation of the above approach :
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Function to find maximum product of a triplet
// in array of integers of size n
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3) {
return -1;
}
// First priority queue of default order which is
// lower value -> higher priority
priority_queue<int, vector<int>, greater<int> > pqmin;
// Second priority queue of reverse order
priority_queue<int> pqmax;
// Iterating through array
for (int i = 0; i < n; i++) {
pqmin.push(arr[i]);
pqmax.push(arr[i]);
}
// initializing the maximum
int maximum = pqmax.top();
pqmax.pop();
// Calculating product1
int product1 = maximum * pqmax.top() * pqmax.top();
// Calculating product2
pqmax.push(maximum);
int min1 = pqmin.top();
pqmin.pop();
int min2 = pqmin.top();
pqmin.pop();
int product2 = maximum * min1 * min2;
// Returning the maximum triplet product
return max(product1, product2);
}
// Driver program to test above functions
int main()
{
int arr[] = { -10, -3, 5, 6, -20 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1) {
cout << "No Triplet Exists";
}
else {
cout << "Maximum triplet product is = " << max;
}
return 0;
}
// Java program to find a maximum product of a
// triplet in array of integers
import java.util.*;
class GFG {
/* Function to find maximum product of a triplet
in array of integers of size n */
static int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3) {
return -1;
}
// first priority queue of default order which is
// lower value -> higher prioirty
PriorityQueue<Integer> pqmin
= new PriorityQueue<>();
// second priority queue of rever order
PriorityQueue<Integer> pqmax = new PriorityQueue<>(
Comparator.reverseOrder());
// iterating through array
for (int i = 0; i < arr.length; i++) {
pqmin.add(arr[i]);
pqmax.add(arr[i]);
}
// initializing the maximum
int maximum = pqmax.poll();
// calculating product1
int product1
= maximum * pqmax.poll() * pqmax.poll();
// calculating product2
int product2
= maximum * pqmin.poll() * pqmin.poll();
// returning the maximum triplet product
return product1 > product2 ? product1 : product2;
}
// Driver program to test above functions
public static void main(String[] args)
{
int arr[] = { -10, -3, 5, 6, -20 };
int n = arr.length;
int max = maxProduct(arr, n);
if (max == -1) {
System.out.println("No Triplet Exists");
}
else {
System.out.println(
"Maximum triplet product is = " + max);
}
}
}
/* This Java code is contributed by JATIN THAKUR*/
import heapq
def maxProduct(arr):
# if size is less than 3, no triplet exists
if len(arr) < 3:
return -1
# First priority queue of default order which is
# lower value -> higher priority
pqmin = []
# Second priority queue of reverse order
pqmax = []
# Iterating through array
for i in range(len(arr)):
heapq.heappush(pqmin, arr[i])
heapq.heappush(pqmax, -arr[i])
# initializing the maximum
maximum = -heapq.heappop(pqmax)
# Calculating product1
product1 = maximum * (-pqmax[0]) * (-pqmax[1])
# Calculating product2
heapq.heappush(pqmax, -maximum)
min1 = heapq.heappop(pqmin)
min2 = heapq.heappop(pqmin)
product2 = maximum * min1 * min2
# Returning the maximum triplet product
return max(product1, product2)
# Driver program to test above functions
arr = [-10, -3, 5, 6, -20]
max = maxProduct(arr)
if max == -1:
print("No Triplet Exists")
else:
print("Maximum triplet product is =", max)
// C# code for the approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// Function to find maximum product of a triplet in
// array of integers of size n
static int MaxProduct(int[] arr, int n)
{
// if size is less than 3, no triplet exists
if (n < 3) {
return -1;
}
// First priority queue of default order which is
// lower value -> higher priority
var pqmin = new SortedSet<int>();
// Second priority queue of reverse order
var pqmax = new SortedSet<int>(Comparer<int>.Create(
(x, y) => y.CompareTo(x)));
// Iterating through array
foreach(var item in arr) {
pqmin.Add(item);
pqmax.Add(item);
}
// initializing the maximum
var maximum = pqmax.First();
pqmax.Remove(maximum);
// Calculating product1
var product1
= maximum * pqmax.First() * pqmax.First();
// Calculating product2
pqmax.Add(maximum);
var min1 = pqmin.Min;
pqmin.Remove(min1);
var min2 = pqmin.Min;
pqmin.Remove(min2);
var product2 = maximum * min1 * min2;
// Returning the maximum triplet product
return Math.Max(product1, product2);
}
// Driver program to test above functions
static void Main() {
// Initializing an integer array
var arr = new int[] { -10, -3, 5, 6, -20 };
// Calculating the length of the array
var n = arr.Length;
// Finding the maximum triplet product
var max = MaxProduct(arr, n);
// Printing the result
if (max == -1) {
Console.WriteLine("No Triplet Exists");
}
else {
Console.WriteLine(
$"Maximum triplet product is = {max}");
}
}
}
class PriorityQueueMin {
constructor() {
this.queue = [];
}
push(value) {
this.queue.push(value);
this.queue.sort((a, b) => a - b);
}
pop() {
return this.queue.shift();
}
peek() {
return this.queue[0];
}
isEmpty() {
return this.queue.length === 0;
}
}
class PriorityQueueMax {
constructor() {
this.queue = [];
}
push(value) {
this.queue.push(value);
this.queue.sort((a, b) => b - a);
}
pop() {
return this.queue.shift();
}
peek() {
return this.queue[0];
}
isEmpty() {
return this.queue.length === 0;
}
}
// This function finds the maximum product of a triplet in an array of integers.
function maxProduct(arr, n) {
// If the array size is less than 3, no triplet exists.
if (n < 3) {
return -1;
}
// Create separate priority queues for storing the smallest elements and the largest elements.
const pqMin = new PriorityQueueMin();
const pqMax = new PriorityQueueMax();
// Iterate through the array and add each element to the appropriate priority queue.
for (let i = 0; i < n; i++) {
pqMin.push(arr[i]);
pqMax.push(arr[i]);
}
// Get the top element from the largest priority queue.
const max = pqMax.peek();
pqMax.pop();
// Calculate the first product, which is the product of the top three
// elements in the largest priority queue.
const product1 = max * pqMax.peek() * pqMax.peek();
// Push the top element back to the largest priority queue.
pqMax.push(max);
// Get the two smallest elements from the smallest priority queue.
const min1 = pqMin.peek();
pqMin.pop();
const min2 = pqMin.peek();
// Calculate the second product, which considers the possibility of two negative numbers.
const product2 = max * min1 * min2;
// Return the maximum of the two products.
return Math.max(product1, product2);
}
// Driver program to test above functions
const arr = [-10, -3, 5, 6, -20];
const n = arr.length;
const max = maxProduct(arr, n);
// Expected output: -2000
console.log("Maximum triplet product is = " + max);
Output
Maximum triplet product is = 1200
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach 4:
- Sort the array using some efficient in-place sorting algorithm in ascending order.
- Return the maximum product of the last three elements of the array and the product of the first two elements and last element.
Below is the implementation of the above approach :
// A C++ program to find a maximum product of a
// triplet in array of integers
#include <bits/stdc++.h>
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Sort the array in ascending order
sort(arr, arr + n);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver program to test above functions
int main()
{
int arr[] = { -10, -3, 5, 6, -20 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout << "No Triplet Exists";
else
cout << "Maximum product is " << max;
return 0;
}
// Java program to find a maximum product of a
// triplet in array of integers
import java.util.Arrays;
class GFG {
/* Function to find a maximum product of a triplet
in array of integers of size n */
static int maxProduct(int arr[], int n) {
// if size is less than 3, no triplet exists
if (n < 3) {
return -1;
}
// Sort the array in ascending order
Arrays.sort(arr);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return Math.max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver program to test above functions
public static void main(String[] args) {
int arr[] = {-10, -3, 5, 6, -20};
int n = arr.length;
int max = maxProduct(arr, n);
if (max == -1) {
System.out.println("No Triplet Exists");
} else {
System.out.println("Maximum product is " + max);
}
}
}
/* This Java code is contributed by Rajput-Ji*/
# A Python3 program to find a maximum
# product of a triplet in an array of integers
# Function to find a maximum product of a
# triplet in array of integers of size n
def maxProduct(arr, n):
# if size is less than 3, no triplet exists
if n < 3:
return -1
# Sort the array in ascending order
arr.sort()
# Return the maximum of product of last
# three elements and product of first
# two elements and last element
return max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3])
# Driver Code
if __name__ == "__main__":
arr = [-10, -3, 5, 6, -20]
n = len(arr)
_max = maxProduct(arr, n)
if _max == -1:
print("No Triplet Exists")
else:
print("Maximum product is", _max)
# This code is contributed by Rituraj Jain
// C# program to find a maximum product of a
// triplet in array of integers
using System;
public class GFG {
/* Function to find a maximum product of a triplet
in array of integers of size n */
static int maxProduct(int []arr, int n) {
// if size is less than 3, no triplet exists
if (n < 3) {
return -1;
}
// Sort the array in ascending order
Array.Sort(arr);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return Math.Max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver program to test above functions
public static void Main() {
int []arr = {-10, -3, 5, 6, -20};
int n = arr.Length;
int max = maxProduct(arr, n);
if (max == -1) {
Console.WriteLine("No Triplet Exists");
} else {
Console.WriteLine("Maximum product is " + max);
}
}
}
// This code is contributed by 29AjayKumar
<script>
// Javascript program to find a maximum
// product of a triplet in array of integers
// Function to find a maximum product of a
// triplet in array of integers of size n
function maxProduct(arr, n)
{
// If size is less than 3, no
// triplet exists
if (n < 3)
{
return -1;
}
// Sort the array in ascending order
arr.sort();
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return Math.max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver code
var arr = [-10, -3, 5, 6, -20];
var n = arr.length;
var max = maxProduct(arr, n);
if (max == -1)
{
document.write("No Triplet Exists");
}
else
{
document.write("Maximum product is " + max);
}
// This code is contributed by Rajput-Ji
</script>
<?php
// PHP program to find a maximum product of a
// triplet in array of integers
/* Function to find a maximum product of a triplet
in array of integers of size n */
function maxProduct($arr, $n)
// if size is less than 3, no triplet exists
{
if ($n < 3)
{
return -1;
}
// Sort the array in ascending order
sort($arr);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return max($arr[0] * $arr[1] * $arr[$n - 1],
$arr[$n - 1] * $arr[$n - 2] * $arr[$n - 3]);
}
// Driver code
$arr = array(-10, -3, 5, 6, -20);
$n = sizeof($arr);
$max = maxProduct($arr, $n);
if ($max == -1)
{
echo("No Triplet Exists");
}
else
{
echo("Maximum product is " . $max);
}
/* This code is contributed by Code_Mech*/
Output
Maximum product is 1200
Time Complexity: O(n log(n))
Auxiliary Space: O(1)
Approach 5:
- Scan the array and compute the Maximum, second maximum and third maximum element present in the array.
- Scan the array and compute Minimum and second minimum element present in the array.
- Return the maximum of product of Maximum, second maximum and third maximum and product of Minimum, second minimum and Maximum element.
Note: Step 1 and Step 2 can be done in a single traversal of the array.
Below is the implementation of the above approach :
// A O(n) C++ program to find maximum product pair in
// an array.
#include <bits/stdc++.h>
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n)
{
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Initialize Maximum, second maximum and third
// maximum element
int maxA = INT_MIN, maxB = INT_MIN, maxC = INT_MIN;
// Initialize Minimum and second minimum element
int minA = INT_MAX, minB = INT_MAX;
for (int i = 0; i < n; i++)
{
// Update Maximum, second maximum and third
// maximum element
if (arr[i] > maxA)
{
maxC = maxB;
maxB = maxA;
maxA = arr[i];
}
// Update second maximum and third maximum element
else if (arr[i] > maxB)
{
maxC = maxB;
maxB = arr[i];
}
// Update third maximum element
else if (arr[i] > maxC)
maxC = arr[i];
// Update Minimum and second minimum element
if (arr[i] < minA)
{
minB = minA;
minA = arr[i];
}
// Update second minimum element
else if(arr[i] < minB)
minB = arr[i];
}
return max(minA * minB * maxA,
maxA * maxB * maxC);
}
// Driver program to test above function
int main()
{
int arr[] = { 1, -4, 3, -6, 7, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout << "No Triplet Exists";
else
cout << "Maximum product is " << max;
return 0;
}
// A O(n) Java program to find maximum product
// pair in an array.
import java.util.*;
class GFG{
// Function to find a maximum product of
// a triplet in array of integers of size n
static int maxProduct(int []arr, int n)
{
// If size is less than 3, no triplet exists
if (n < 3)
return -1;
// Initialize Maximum, second maximum
// and third maximum element
int maxA = Integer.MIN_VALUE,
maxB = Integer.MIN_VALUE,
maxC = Integer.MIN_VALUE;
// Initialize Minimum and
// second minimum element
int minA = Integer.MAX_VALUE,
minB = Integer.MAX_VALUE;
for(int i = 0; i < n; i++)
{
// Update Maximum, second maximum
// and third maximum element
if (arr[i] > maxA)
{
maxC = maxB;
maxB = maxA;
maxA = arr[i];
}
// Update second maximum and
// third maximum element
else if (arr[i] > maxB)
{
maxC = maxB;
maxB = arr[i];
}
// Update third maximum element
else if (arr[i] > maxC)
maxC = arr[i];
// Update Minimum and second
// minimum element
if (arr[i] < minA)
{
minB = minA;
minA = arr[i];
}
// Update second minimum element
else if(arr[i] < minB)
minB = arr[i];
}
return Math.max(minA * minB * maxA,
maxA * maxB * maxC);
}
// Driver code
public static void main(String[] args)
{
int []arr = { 1, -4, 3, -6, 7, 0 };
int n = arr.length;
int max = maxProduct(arr, n);
if (max == -1)
System.out.print("No Triplet Exists");
else
System.out.print("Maximum product is " + max);
}
}
// This code is contributed by pratham76
# A O(n) Python3 program to find maximum
# product pair in an array.
import sys
# Function to find a maximum product
# of a triplet in array of integers
# of size n
def maxProduct(arr, n):
# If size is less than 3, no
# triplet exists
if n < 3:
return -1
# Initialize Maximum, second
# maximum and third maximum
# element
maxA = -sys.maxsize - 1
maxB = -sys.maxsize - 1
maxC = -sys.maxsize - 1
# Initialize Minimum and
# second minimum element
minA = sys.maxsize
minB = sys.maxsize
for i in range(n):
# Update Maximum, second
# maximum and third maximum
# element
if arr[i] > maxA:
maxC = maxB
maxB = maxA
maxA = arr[i]
# Update second maximum and
# third maximum element
elif arr[i] > maxB:
maxC = maxB
maxB = arr[i]
# Update third maximum element
elif arr[i] > maxC:
maxC = arr[i]
# Update Minimum and second
# minimum element
if arr[i] < minA:
minB = minA
minA = arr[i]
# Update second minimum element
elif arr[i] < minB:
minB = arr[i]
return max(minA * minB * maxA,
maxA * maxB * maxC)
# Driver Code
arr = [ 1, -4, 3, -6, 7, 0 ]
n = len(arr)
Max = maxProduct(arr, n)
if Max == -1:
print("No Triplet Exists")
else:
print("Maximum product is", Max)
# This code is contributed by avanitrachhadiya2155 & RidaZouga
// A O(n) C# program to find maximum product
// pair in an array.
using System;
using System.Collections;
class GFG{
// Function to find a maximum product of
// a triplet in array of integers of size n
static int maxProduct(int []arr, int n)
{
// If size is less than 3, no triplet exists
if (n < 3)
return -1;
// Initialize Maximum, second maximum
// and third maximum element
int maxA = Int32.MinValue,
maxB = Int32.MinValue,
maxC = Int32.MinValue;
// Initialize Minimum and
// second minimum element
int minA = Int32.MaxValue,
minB = Int32.MaxValue;
for(int i = 0; i < n; i++)
{
// Update Maximum, second maximum
// and third maximum element
if (arr[i] > maxA)
{
maxC = maxB;
maxB = maxA;
maxA = arr[i];
}
// Update second maximum and
// third maximum element
else if (arr[i] > maxB)
{
maxC = maxB;
maxB = arr[i];
}
// Update third maximum element
else if (arr[i] > maxC)
maxC = arr[i];
// Update Minimum and second
// minimum element
if (arr[i] < minA)
{
minB = minA;
minA = arr[i];
}
// Update second minimum element
else if(arr[i] < minB)
minB = arr[i];
}
return Math.Max(minA * minB * maxA,
maxA * maxB * maxC);
}
// Driver code
public static void Main(string[] args)
{
int []arr = { 1, -4, 3, -6, 7, 0 };
int n = arr.Length;
int max = maxProduct(arr, n);
if (max == -1)
Console.Write("No Triplet Exists");
else
Console.Write("Maximum product is " + max);
}
}
// This code is contributed by rutvik_56
<script>
// A O(n) javascript program to find maximum product
// pair in an array.
// Function to find a maximum product of
// a triplet in array of integers of size n
function maxProduct(arr , n)
{
// If size is less than 3, no triplet exists
if (n < 3)
return -1;
// Initialize Maximum, second maximum
// and third maximum element
var maxA = Number.MIN_VALUE,
maxB = Number.MIN_VALUE,
maxC = Number.MIN_VALUE;
// Initialize Minimum and
// second minimum element
var minA = Number.MAX_VALUE,
minB = Number.MAX_VALUE;
for(i = 0; i < n; i++)
{
// Update Maximum, second maximum
// and third maximum element
if (arr[i] > maxA)
{
maxC = maxB;
maxB = maxA;
maxA = arr[i];
}
// Update second maximum and
// third maximum element
else if (arr[i] > maxB)
{
maxC = maxB;
maxB = arr[i];
}
// Update third maximum element
else if (arr[i] > maxC)
maxC = arr[i];
// Update Minimum and second
// minimum element
if (arr[i] < minA)
{
minB = minA;
minA = arr[i];
}
// Update second minimum element
else if(arr[i] < minB)
minB = arr[i];
}
return Math.max(minA * minB * maxA,
maxA * maxB * maxC);
}
// Driver code
var arr = [ 1, -4, 3, -6, 7, 0 ];
var n = arr.length;
var max = maxProduct(arr, n);
if (max == -1)
document.write("No Triplet Exists");
else
document.write("Maximum product is " + max);
// This code is contributed by 29AjayKumar
</script>
Output
Maximum product is 168
Time Complexity: O(n)
Auxiliary Space: O(1)
Exercise:
1. Print the triplet that has a maximum product.
2. Find a minimum product of a triplet in the array.