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 tripletlong 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 Codeint 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 approachimport 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 approachimport sys;# Function to minimize the sum of# price by taking a tripletdef 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 codeif __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 approachusing System;class GFG{// Function to minimize the sum of// price by taking a tripletpublic 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 Codepublic 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
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 tripletlong 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 Codeint 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 Codenum = [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 tripletfunction minSum(n, num, price) {// Initialize a dp[] arraylet dp = [Infinity, Infinity];// Stores the final resultlet ans = Infinity;// Iterate for all values till Nfor (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 ansreturn ans != Infinity ? ans : -1;}// Driver Codelet num = [2, 4, 6, 7, 8];let price = [10, 20, 100, 20, 40];let n = price.length;console.log(minSum(n, num, price)); |
Output
50
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
