Minimum possible sum of prices of a Triplet from the given Array

0 0 10 minutes read

Given an array num[] of N integers where each element is associated with a price given by another array price[], the task is to minimize the sum of price by taking a triplet such that num[i] < num[j] < num[k]. If there is no such triplet then print -1.

Examples:

Input: num[]={2, 4, 6, 7, 8}, price[]={10, 20, 100, 20, 40}
Output: 50
Explanation:
Selecting the triplet {2, 4, 7} because (2 < 4 < 7), and the price is 10 + 20 + 20 = 50 which is the minimum possible.

Input: num[]={100, 101, 100}, price[]={2, 4, 5}
Output: -1
Explanation:
No possible triplet exists.

Naive Approach:
The simplest approach is to generate all possible triplets (i, j, k) such that i < j < k and num[i] < num[j] < num[k] then find the sum of prices[i], prices[j], and prices[k]. Print the minimum sum of all such triplets.

Time Complexity: O(N³)
Auxiliary Space: O(1)

Efficient Approach: The idea is to use auxiliary array dp[] to store the minimum sum of prices of all such triplets and print the minimum of all the prices stored in it. Below are the steps:

Initialize the dp[] array to INT_MAX.
Initialize the current minimum sum(say current_sum) to INT_MAX.
Generate all possible pairs (i, j) such that j > i. If nums[j] > num[i] then update dp[j] = min(dp[j], price[i] + price[j]) as this is one of the possible pairs.
In each pair (i, j) in the above steps update the minimum sum of triplets to min(current_sum, dp[i] + price[j]). This step will ensure that the possible triplets (i, j, k) is formed as dp[i] will store the sum of the price at index i and j, and j is the value of k.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
 
// Function to minimize the sum of
// price by taking a triplet
long minSum(int n, int num[], int price[])
{
     
    // Initialize a dp[] array
    long dp[n];
 
    for(int i = 0; i < n; i++)
        dp[i] = INT_MAX;
 
    // Stores the final result
    long ans = INT_MAX;
 
    // Iterate for all values till N
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
             
            // Check if num[j] > num[i]
            if (num[j] > num[i]) 
            {
                 
                // Update dp[j] if it is
                // greater than stored value
                dp[j] = (long)min((long)dp[j],
                                  (long)price[i] +
                                  (long)price[j]);
 
                // Update the minimum
                // sum as ans
                ans = min(ans, (long)dp[i] +
                               (long)price[j]);
            }
        }
    }
     
    // If there is no minimum sum exist
    // then print -1 else print the ans
    return ans != INT_MAX ? ans : -1;
}
 
// Driver Code
int main()
{
    int num[] = { 2, 4, 6, 7, 8 };
    int price[] = { 10, 20, 100, 20, 40 };
     
    int n = sizeof(price) / sizeof(price[0]);
     
    cout << (minSum(n, num, price));
}
 
// This code is contributed by chitranayal

Java

// Java Program to implement
// the above approach
import java.util.*;
import java.io.*;
 
public class Main {
 
    // Function to minimize the sum of
    // price by taking a triplet
    public static long minSum(int n, int num[],
                              int price[])
    {
 
        // Initialize a dp[] array
        long dp[] = new long[n];
 
        Arrays.fill(dp, Integer.MAX_VALUE);
 
        // Stores the final result
        long ans = Integer.MAX_VALUE;
 
        // Iterate for all values till N
        for (int i = 0; i < n; i++) {
 
            for (int j = i + 1; j < n; j++) {
 
                // Check if num[j] > num[i]
                if (num[j] > num[i]) {
 
                    // Update dp[j] if it is
                    // greater than stored value
                    dp[j] = (long)Math.min(
                        (long)dp[j],
                        (long)price[i]
                            + (long)price[j]);
 
                    // Update the minimum
                    // sum as ans
                    ans = Math.min(
                        ans, (long)dp[i]
                                 + (long)price[j]);
                   
                }
            }
        }
       
 
        // If there is no minimum sum exist
        // then print -1 else print the ans
        return ans != Integer.MAX_VALUE ? ans : -1;
    }
 
    // Driver Code
    public static void
        main(String[] args)
    {
 
        int num[] = { 2, 4, 6, 7, 8 };
        int price[] = { 10, 20, 100, 20, 40 };
 
        int n = price.length;
 
        System.out.println(minSum(n, num, price));
    }
}

Python3

# Python3 program to implement
# the above approach
import sys;
 
# Function to minimize the sum of
# price by taking a triplet
def minSum(n, num, price):
     
    # Initialize a dp[] list
    dp = [0 for i in range(n)]
    for i in range(n):
        dp[i] = sys.maxsize
 
    # Stores the final result
    ans = sys.maxsize
 
    # Iterate for all values till N
    for i in range(n):
        for j in range(i + 1, n):
             
            # Check if num[j] > num[i]
            if (num[j] > num[i]):
                 
                # Update dp[j] if it is
                # greater than stored value
                dp[j] = min(dp[j], price[i] +
                                   price[j])
 
                # Update the minimum
                # sum as ans
                ans = min(ans, dp[i] + price[j])
                 
    # If there is no minimum sum exist
    # then print -1 else print the ans
    if ans is not sys.maxsize:
        return ans
    else:
        return -1
 
# Driver code
if __name__=='__main__':
     
    num = [ 2, 4, 6, 7, 8 ]
    price = [ 10, 20, 100, 20, 40 ]
     
    n = len(price)
     
    print(minSum(n, num, price))
 
# This code is contributed by rutvik_56

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to minimize the sum of
// price by taking a triplet
public static long minSum(int n, int []num,
                          int []price)
{
     
    // Initialize a []dp array
    long []dp = new long[n];
    for(int i = 0; i < n; i++)
        dp[i] = int.MaxValue;
 
    // Stores the readonly result
    long ans = int.MaxValue;
 
    // Iterate for all values till N
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
 
            // Check if num[j] > num[i]
            if (num[j] > num[i]) 
            {
 
                // Update dp[j] if it is
                // greater than stored value
                dp[j] = (long)Math.Min((long)dp[j],
                                       (long)price[i] +
                                       (long)price[j]);
 
                // Update the minimum
                // sum as ans
                ans = Math.Min(ans, (long)dp[i] +
                                    (long)price[j]);
            }
        }
    }
     
    // If there is no minimum sum exist
    // then print -1 else print the ans
    return ans != int.MaxValue ? ans : -1;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []num = { 2, 4, 6, 7, 8 };
    int []price = { 10, 20, 100, 20, 40 };
 
    int n = price.Length;
 
    Console.WriteLine(minSum(n, num, price));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// JavaScript program for the above approach
 
    // Function to minimize the sum of
    // price by taking a triplet
    function minSum(n, num, price)
    {
   
        // Initialize a dp[] array
        let dp = Array.from({length: n}, (_, i) => Number.MAX_VALUE);
     
        // Stores the final result
        let ans = Number.MAX_VALUE;
   
        // Iterate for all values till N
        for (let i = 0; i < n; i++) {
   
            for (let j = i + 1; j < n; j++) {
   
                // Check if num[j] > num[i]
                if (num[j] > num[i]) {
   
                    // Update dp[j] if it is
                    // greater than stored value
                    dp[j] = Math.min(
                        dp[j],
                        price[i]
                            + price[j]);
   
                    // Update the minimum
                    // sum as ans
                    ans = Math.min(
                        ans, dp[i]
                                 + price[j]);
                     
                }
            }
        }
         
   
        // If there is no minimum sum exist
        // then print -1 else print the ans
        return ans != Number.MAX_VALUE ? ans : -1;
    }
    
 
// Driver Code    
     
        let num = [ 2, 4, 6, 7, 8 ];
        let price = [ 10, 20, 100, 20, 40 ];
   
        let n = price.length;
   
        document.write(minSum(n, num, price));
                   
</script>

Output

Time Complexity: O(N²)
Auxiliary Space: O(N)

Efficient approach : Space optimization O(1)

To optimize the space complexity since we only need to access the values of dp[i] and dp[i-1] to compute dp[i+1], we can just use two variables to store these values instead of an entire array. This way, the space complexity will be reduced from O(N) to O(1)

Implementation Steps:

We can observe that we only need to keep track of the two most recent values of dp[j] for a given i.
Therefore, we can replace the dp[] array with just two variables, dp[0] and dp[1].
We can initialize both variables to INT_MAX at the start of each iteration of i.
In the inner loop, we can update dp[1] instead of dp[j], and update ans using dp[0] instead of dp[i].
At the end of each iteration of i, we can copy the value of dp[1] to dp[0] and reset dp[1] to INT_MAX.
At last return -1 if ans is still INT_MAX, or return ans.

Implementation:

C++

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to minimize the sum of
// price by taking a triplet
long minSum(int n, int num[], int price[])
{
    // Initialize a dp[] array
    long dp[2];
 
    for (int i = 0; i < 2; i++)
        dp[i] = INT_MAX;
 
    // Stores the final result
    long ans = INT_MAX;
 
    // Iterate for all values till N
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // Check if num[j] > num[i]
            if (num[j] > num[i]) {
 
                // Update dp[j] if it is
                // greater than stored value
                dp[1] = (long)min((long)dp[1],
                                  (long)price[i]
                                      + (long)price[j]);
 
                // Update the minimum
                // sum as ans
                ans = min(ans,
                          (long)dp[0] + (long)price[j]);
            }
        }
        // Copy dp[1] to dp[0] for the next iteration
        dp[0] = dp[1];
        dp[1] = INT_MAX;
    }
 
    // If there is no minimum sum exist
    // then print -1 else print the ans
    return ans != INT_MAX ? ans : -1;
    return ans != INT_MAX ? ans : -1;
}
 
// Driver Code
int main()
{
    int num[] = { 2, 4, 6, 7, 8 };
    int price[] = { 10, 20, 100, 20, 40 };
 
    int n = sizeof(price) / sizeof(price[0]);
 
    cout << (minSum(n, num, price));
}
// this code is contributed by bhardwajji

Java

public class Main {
 
    // Function to minimize the sum of price by taking a triplet
    public static long minSum(int n, int[] num, int[] price) {
        long[] dp = new long[2];
 
        // Initialize dp[] array
        for (int i = 0; i < 2; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
 
        // Stores the final result
        long ans = Integer.MAX_VALUE;
 
        // Iterate for all values till N
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Check if num[j] > num[i]
                if (num[j] > num[i]) {
                    // Update dp[j] if it is greater than the stored value
                    dp[1] = Math.min(dp[1], (long) price[i] + (long) price[j]);
 
                    // Update the minimum sum as ans
                    ans = Math.min(ans, (long) dp[0] + (long) price[j]);
                }
            }
            // Copy dp[1] to dp[0] for the next iteration
            dp[0] = dp[1];
            dp[1] = Integer.MAX_VALUE;
        }
 
        // If there is no minimum sum exist then return -1, else return the ans
        return ans != Integer.MAX_VALUE ? ans : -1;
    }
 
    public static void main(String[] args) {
        int[] num = {2, 4, 6, 7, 8};
        int[] price = {10, 20, 100, 20, 40};
 
        int n = price.length;
 
        System.out.println(minSum(n, num, price));
    }
}

Python

def min_sum(n, num, price):
    # Initialize a dp[] array
    dp = [float('inf')] * 2
 
    # Stores the final result
    ans = float('inf')
 
    # Iterate for all values till N
    for i in range(n):
        for j in range(i + 1, n):
            # Check if num[j] > num[i]
            if num[j] > num[i]:
                # Update dp[j] if it is greater than stored value
                dp[1] = min(dp[1], price[i] + price[j])
                # Update the minimum sum as ans
                ans = min(ans, dp[0] + price[j])
 
        # Copy dp[1] to dp[0] for the next iteration
        dp[0], dp[1] = dp[1], float('inf')
 
    # If there is no minimum sum exist then return -1, else return the ans
    return ans if ans != float('inf') else -1
 
 
# Driver Code
num = [2, 4, 6, 7, 8]
price = [10, 20, 100, 20, 40]
n = len(price)
 
print(min_sum(n, num, price))

C#

using System;
 
class Program
{
 // Function to minimize the sum of
// price by taking a triplet
    static long MinSum(int n, int[] num, int[] price)
    {
      // Initialize a dp[] array
        long[] dp = new long[2];
        for (int i = 0; i < 2; i++)
            dp[i] = int.MaxValue;
        // Stores the final result
        long ans = int.MaxValue;
        // Iterate for all values till N
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (num[j] > num[i])
                {
                    dp[1] = Math.Min(dp[1], (long)price[i] + (long)price[j]);
                    ans = Math.Min(ans, (long)dp[0] + (long)price[j]);
                }
            }
 
            dp[0] = dp[1];
            dp[1] = int.MaxValue;
        }
 
        return ans != int.MaxValue ? ans : -1;
    }
 
    static void Main(string[] args)
    {
        int[] num = { 2, 4, 6, 7, 8 };
        int[] price = { 10, 20, 100, 20, 40 };
 
        int n = price.Length;
 
        Console.WriteLine(MinSum(n, num, price));
    }
}

Javascript

// Function to minimize the sum of
// price by taking a triplet
function minSum(n, num, price) {
// Initialize a dp[] array
let dp = [Infinity, Infinity];
// Stores the final result
let ans = Infinity;
 
// Iterate for all values till N
for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
 
        // Check if num[j] > num[i]
        if (num[j] > num[i]) {
 
            // Update dp[j] if it is
            // greater than stored value
            dp[1] = Math.min(dp[1], price[i] + price[j]);
 
            // Update the minimum
            // sum as ans
            ans = Math.min(ans, dp[0] + price[j]);
        }
    }
    // Copy dp[1] to dp[0] for the next iteration
    dp[0] = dp[1];
    dp[1] = Infinity;
}
 
// If there is no minimum sum exist
// then print -1 else print the ans
return ans != Infinity ? ans : -1;
}
 
// Driver Code
let num = [2, 4, 6, 7, 8];
let price = [10, 20, 100, 20, 40];
 
let n = price.length;
 
console.log(minSum(n, num, price));

Output

Time Complexity: O(N^2)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!