Minimum possible sum of prices of a Triplet from the given Array
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(N3)
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> |
50
Time Complexity: O(N2)
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)); |
50
Time Complexity: O(N^2)
Auxiliary Space: O(1)