Minimum cost for gift card eligibility from Contiguous Subsegments
Given a list of prices for n products, find the minimum amount a customer needs to spend to obtain a gift card. A gift card is awarded when a customer purchases a contiguous subsegment of products, and at least two products within that subsegment have matching prices. If it’s not possible for any customer to receive a gift card, return -1.
Examples:
Input: prices[] = [1, 2, 3, 1, 2, 1]
Output: 4
Explanation: Buying products from index 3 to 5, which includes products [1, 2, 1]. Two of these products have a matching price.Input: prices[] = [1, 2, 1, 2]
Output: 4
Explanation: Buying products from index 0 to 3, which includes products [1, 2, 1]. Two of these products have a matching price.
Input: prices[] = [1, 100, 1, 7, 7]
Output: 14
Explanation: Buying products from index 3 to 4, which includes products [7, 7]. Two of these products have a matching price.
Approach: To solve the problem follow the below idea:
Find prefix sum of prices and then identify the indices of products with matching prices
Steps to solve the problem:
- First, Calculate prefix sum of prices and store it in prefix_sum vector.
- Use unordered_map to store indices of products with the same price
- Declare constants INF and res for calculating minimum price.
- Now loop through these indices, comparing pairs to identify contiguous subsegments.
- For each pair of indices, we first calculate the cost by subtracting the prefix sum at the left index from the prefix sum at the right index.
- The minimum cost among all subsegments is updated in res.
- After the loops, if res remains as “infinity,” it returns -1, Otherwise, it returns the minimum cost calculated.
Below is the implementation of the approach:
C++
// C++ code for the above approach: #include <climits> #include <iostream> #include <unordered_map> #include <vector> using namespace std; int findMinimumPrice(vector< int > price) { int n = price.size(); vector< long long > prefix_sum(n, 0); for ( int i = 0; i < n; i++) { if (i - 1 >= 0) { prefix_sum[i] += prefix_sum[i - 1]; } prefix_sum[i] += price[i]; } unordered_map< int , vector< int > > idxs; for ( int i = 0; i < n; i++) { idxs[price[i]].push_back(i); } long long INF = LLONG_MAX; long long res = INF; for ( const auto & pair : idxs) { int key = pair.first; vector< int > value = pair.second; int m = value.size(); for ( int i = 0; i < m; i++) { if (i + 1 < m) { int left_index = value[i]; int right_index = value[i + 1]; res = min( res, prefix_sum[right_index] - (left_index - 1 >= 0 ? prefix_sum[left_index - 1] : 0)); } } } return res == INF ? -1 : static_cast < int >(res); } // Drivers code int main() { vector< int > prices = { 1, 3, 2, 2, 2, 3 }; int minPrice = findMinimumPrice(prices); // Function Call if (minPrice == -1) { cout << "No minimum price found." << endl; } else { cout << "Minimum price: " << minPrice << endl; } return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { public static int findMinimumPrice(List<Integer> price) { int n = price.size(); List<Long> prefixSum = new ArrayList<>(); for ( int i = 0 ; i < n; i++) { if (i - 1 >= 0 ) { prefixSum.add(prefixSum.get(i - 1 ) + price.get(i)); } else { prefixSum.add(( long )price.get(i)); } } Map<Integer, List<Integer> > idxs = new HashMap<>(); for ( int i = 0 ; i < n; i++) { int value = price.get(i); if (!idxs.containsKey(value)) { idxs.put(value, new ArrayList<>()); } idxs.get(value).add(i); } long INF = Long.MAX_VALUE; long res = INF; for (Map.Entry<Integer, List<Integer> > entry : idxs.entrySet()) { int key = entry.getKey(); List<Integer> value = entry.getValue(); int m = value.size(); for ( int i = 0 ; i < m; i++) { if (i + 1 < m) { int leftIndex = value.get(i); int rightIndex = value.get(i + 1 ); res = Math.min( res, prefixSum.get(rightIndex) - (leftIndex - 1 >= 0 ? prefixSum.get( leftIndex - 1 ) : 0 )); } } } return res == INF ? - 1 : ( int )res; } public static void main(String[] args) { List<Integer> prices = Arrays.asList( 1 , 3 , 2 , 2 , 2 , 3 ); int minPrice = findMinimumPrice(prices); // Function Call if (minPrice == - 1 ) { System.out.println( "No minimum price found." ); } else { System.out.println( "Minimum price: " + minPrice); } } } // This code is contributed by Abhinav Mahajan // (abhinav_m22). |
Python3
def find_minimum_price(prices): n = len (prices) prefix_sum = [ 0 ] * n # Calculate the prefix sum of prices for i in range (n): if i - 1 > = 0 : prefix_sum[i] = prefix_sum[i - 1 ] + prices[i] else : prefix_sum[i] = prices[i] # Create a dictionary to store indices of each price idxs = {} for i in range (n): value = prices[i] if value not in idxs: idxs[value] = [] idxs[value].append(i) INF = float ( 'inf' ) res = INF # Iterate through the dictionary entries for key, value in idxs.items(): m = len (value) # Iterate through the indices of each price for i in range (m - 1 ): left_index = value[i] right_index = value[i + 1 ] res = min (res, prefix_sum[right_index] - (prefix_sum[left_index - 1 ] if left_index - 1 > = 0 else 0 )) return - 1 if res = = INF else int (res) # Driver code prices = [ 1 , 3 , 2 , 2 , 2 , 3 ] min_price = find_minimum_price(prices) # Function Call if min_price = = - 1 : print ( "No minimum price found." ) else : print ( "Minimum price:" , min_price) |
C#
using System; using System.Collections.Generic; using System.Linq; class GFG { public static int FindMinimumPrice(List< int > prices) { int n = prices.Count; List< long > prefixSum = new List< long >(); for ( int i = 0; i < n; i++) { if (i - 1 >= 0) { prefixSum.Add(prefixSum[i - 1] + prices[i]); } else { prefixSum.Add(prices[i]); } } Dictionary< int , List< int >> idxs = new Dictionary< int , List< int >>(); for ( int i = 0; i < n; i++) { int value = prices[i]; if (!idxs.ContainsKey(value)) { idxs[value] = new List< int >(); } idxs[value].Add(i); } long INF = long .MaxValue; long res = INF; foreach ( var entry in idxs) { int key = entry.Key; List< int > value = entry.Value; int m = value.Count; for ( int i = 0; i < m; i++) { if (i + 1 < m) { int leftIndex = value[i]; int rightIndex = value[i + 1]; res = Math.Min(res, prefixSum[rightIndex] - (leftIndex - 1 >= 0 ? prefixSum[leftIndex - 1] : 0)); } } } return res == INF ? -1 : ( int )res; } public static void Main() { List< int > prices = new List< int > {1, 3, 2, 2, 2, 3}; int minPrice = FindMinimumPrice(prices); // Function Call if (minPrice == -1) { Console.WriteLine( "No minimum price found." ); } else { Console.WriteLine($ "Minimum price: {minPrice}" ); } } } // This code is contributed by Rohit Singh |
Javascript
function findMinimumPrice(price) { const n = price.length; const prefixSum = Array(n).fill(0); for (let i = 0; i < n; i++) { if (i - 1 >= 0) { prefixSum[i] += prefixSum[i - 1]; } prefixSum[i] += price[i]; } const idxs = new Map(); for (let i = 0; i < n; i++) { if (!idxs.has(price[i])) { idxs.set(price[i], []); } idxs.get(price[i]).push(i); } const INF = Number.MAX_SAFE_INTEGER; let res = INF; for (const [key, value] of idxs) { const m = value.length; for (let i = 0; i < m; i++) { if (i + 1 < m) { const leftIndex = value[i]; const rightIndex = value[i + 1]; res = Math.min( res, prefixSum[rightIndex] - (leftIndex - 1 >= 0 ? prefixSum[leftIndex - 1] : 0) ); } } } return res === INF ? -1 : res; } // Driver code const prices = [1, 3, 2, 2, 2, 3]; const minPrice = findMinimumPrice(prices); // Function Call if (minPrice === -1) { console.log( "No minimum price found." ); } else { console.log( "Minimum price:" , minPrice); } |
Minimum price: 4
Time Complexity: O(n), where n is the number of products.
Auxiliary Space: O(n + m), where n is the number of products, and m is the number of unique product prices.