Find triplet having maximum product in an array

Posted in /  

Find triplet having maximum product in an array

Vinay Khatri
Last updated on September 28, 2022

    Problem

    Find 3 numbers from the array such that their product is maximum.

    Sample Input

    [1,2,2,2]

    Sample Output

    8

    Approach

    We can sort the given array and end up on 2 cases:

    Case 1: The maximum product is obtained by the last 3 numbers.

    Case 2: The maximum product is obtained by the first 2 numbers and the last number. We just return a maximum of the above two cases. The time complexity is O(NlogN)

    C++ Programming

     #include<bits/stdc++.h>
     using namespace std;
     
     int maximumProduct(vector<int>& nums) {
            int n = nums.size();
            
           sort(nums.begin(), nums.end()); 
           
            int ans = max(nums[n-3]*nums[n-2]*nums[n-1],nums[0]*nums[1]*nums[n-1]);
            
            return ans;
            
     }
    int main(){
        vector<int>v{1,2,3};
        cout<<maximumProduct(v);
    }

    Output

    6

    Another way to code the same algorithm in C#

    using System;
    
    public class Solution
    {
     public static int solve(int[] nums)
     {
     Array.Sort(nums);
     int last = nums.Length - 1;
    
     int C1 = nums[last] * nums[last - 1] * nums[last - 2];
    
     int C2 = int.MinValue;
     int minNegative1 = nums[0];
     int minNegative2 = nums[1];
     int maxValue = nums[last];
     if (minNegative1 < 0 && minNegative2 < 0)
     {
     C2 = minNegative1 * minNegative2 * maxValue;
     }
    
     return Math.Max(C1, C2);
     }
     static void Main(string[] args){
         int[] arr = {1, 2, 3};
         Console.WriteLine(solve(arr));
     }
    }

    Output

    6

    Python Programming

    def maximumProduct(nums):
        nums.sort()
        return max(nums[0]*nums[1]*nums[-1],nums[-1]*nums[-2]*nums[-3])
    
    l = [1,2,3]
    print(maximumProduct(l))

    Output

    6
    

    People are also reading:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments