Shopping Offers
MedPrompt
In LeetCode Store, there are n items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given an integer array price where price[i] is the price of the ith item, and an integer array needs where needs[i] is the number of pieces of the ith item you want to buy.
You are also given an array special where special[i] is of size n + 1 where special[i][j] is the number of pieces of the jth item in the ith offer and special[i][n] (i.e., the last integer in the array) is the price of the ith offer.
Return the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. You are not allowed to buy more items than you want, even if that would lower the overall price. You could use any of the special offers as many times as you want.
Example 1:
Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14
Explanation: There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.Example 2:
Input: price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
Output: 11
Explanation: The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.
Constraints:
n == price.length == needs.length1 <= n <= 60 <= price[i], needs[i] <= 101 <= special.length <= 100special[i].length == n + 10 <= special[i][j] <= 50- The input is generated that at least one of
special[i][j]is non-zero for0 <= j <= n - 1.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves exploring all possible combinations of applying special offers through a recursive function. For any given state of needs, we have two choices: either buy the remaining items at their individual prices or apply one of the valid special offers. We recursively explore the consequences of applying an offer and take the minimum cost found among all possibilities.
Algorithm
- Define a recursive function
backtrack(price, special, needs)that returns the minimum cost for the givenneeds. - Inside the function, first calculate the cost of buying all items in
needsindividually without any special offers. Let this beminCost. This serves as the initial best price for the current state. - Iterate through each special offer in the
speciallist. - For each offer, check if it can be applied. An offer is applicable if the quantity of each item it provides is less than or equal to the corresponding quantity in the current
needs. - If an offer is applicable, create a new
nextNeedslist by subtracting the items from the offer from the currentneeds. - Make a recursive call:
backtrack(price, special, nextNeeds). The cost for this path is the offer's price plus the result of the recursive call. - Update
minCostto be the minimum of its current value and the cost calculated in the previous step. - After iterating through all offers, return the final
minCost.
Walkthrough
The core idea is a recursive function that calculates the minimum cost for the items listed in the needs vector. This function explores every possible path of applying offers. For a given set of needs, it first computes a baseline cost by assuming no special offers are used. Then, it iterates through all special offers. For each offer that can be validly applied (i.e., we need at least as many items as the offer provides), it calculates a new state of needs and recursively calls itself to find the minimum cost for the remaining items. The total cost for this path is the offer's price plus the cost from the recursive call. The function keeps track of the minimum cost found across all these paths. This method is simple to conceive but inefficient because it recalculates the minimum cost for the same needs state multiple times if that state can be reached through different sequences of offers.
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) { return backtrack(price, special, needs);} private int backtrack(List<Integer> price, List<List<Integer>> special, List<Integer> needs) { int n = price.size(); // Cost without any special offers int minCost = 0; for (int i = 0; i < n; i++) { minCost += needs.get(i) * price.get(i); } // Try to apply each special offer for (List<Integer> offer : special) { List<Integer> nextNeeds = new ArrayList<>(); boolean canApply = true; for (int i = 0; i < n; i++) { if (needs.get(i) < offer.get(i)) { canApply = false; break; } nextNeeds.add(needs.get(i) - offer.get(i)); } if (canApply) { // If offer is applicable, calculate cost with this offer and recurse int costWithOffer = offer.get(n) + backtrack(price, special, nextNeeds); minCost = Math.min(minCost, costWithOffer); } } return minCost;}Complexity
Time
Exponential, roughly O(m^D), where `m` is the number of special offers and `D` is related to the total number of items to buy. The function branches for each applicable offer, leading to an exponential number of calls.
Space
O(D * n), where D is the maximum depth of the recursion and n is the number of item types. This space is consumed by the recursion call stack.
Trade-offs
Pros
Simple to understand and implement as it directly models the decision-making process.
Cons
Extremely inefficient due to redundant computations for the same subproblems (i.e., the same
needsvector).Will likely result in a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial test cases.
This approach optimizes the brute-force recursion by using memoization, a technique central to top-down dynamic programming. It stores the results of subproblems that have already been solved in a cache (like a hash map). By avoiding redundant computations for the same state of needs, it significantly improves performance, making it feasible to solve the problem within typical time limits.
Algorithm
- Initialize a
Map<List<Integer>, Integer> memoto store results of subproblems. - (Optional but recommended) Pre-process the
specialoffers list. Remove any offer where the offer price is greater than or equal to the price of buying its items individually. This prunes the search space. - Define a recursive helper function
solve(price, special, needs). - Inside
solve, first check if the currentneedsstate exists as a key inmemo. If yes, return the stored value. - Calculate the cost of fulfilling
needsby buying all items individually. This is the initialminCost. - Iterate through each (filtered) special offer.
- If an offer is applicable, calculate the
nextNeedsand recursively callsolve(price, special, nextNeeds). - Update
minCostwith the minimum of its current value andoffer_price + recursive_result. - Before returning, store the computed
minCostinmemowith the currentneedsas the key. - Return
minCost.
Walkthrough
We enhance the recursive solution by adding a cache (e.g., a HashMap) to store the minimum cost for each unique needs vector encountered. The needs list serves as the key, and the minimum cost is the value. Before computing the cost for a needs state, we first check if the result is already in our cache. If it is, we return the cached value immediately. Otherwise, we compute the result as in the brute-force approach, and before returning, we store the result in the cache for future use. A useful optimization is to filter out 'useless' special offers beforehand. An offer is useless if its price is more expensive than buying the same items individually. This reduces the number of recursive branches to explore at each step, further improving efficiency.
class Solution { private Map<List<Integer>, Integer> memo; public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) { memo = new HashMap<>(); // Filter out useless offers List<List<Integer>> filteredSpecial = new ArrayList<>(); for (List<Integer> offer : special) { int individualPrice = 0; for (int i = 0; i < price.size(); i++) { individualPrice += offer.get(i) * price.get(i); } if (offer.get(price.size()) < individualPrice) { filteredSpecial.add(offer); } } return solve(price, filteredSpecial, needs); } private int solve(List<Integer> price, List<List<Integer>> special, List<Integer> needs) { if (memo.containsKey(needs)) { return memo.get(needs); } int n = price.size(); // Cost without any special offers int minCost = 0; for (int i = 0; i < n; i++) { minCost += needs.get(i) * price.get(i); } // Try to apply each special offer for (List<Integer> offer : special) { List<Integer> nextNeeds = new ArrayList<>(); boolean canApply = true; for (int i = 0; i < n; i++) { if (needs.get(i) < offer.get(i)) { canApply = false; break; } nextNeeds.add(needs.get(i) - offer.get(i)); } if (canApply) { minCost = Math.min(minCost, offer.get(n) + solve(price, special, nextNeeds)); } } memo.put(needs, minCost); return minCost; }}Complexity
Time
O(S * m * n), where `S` is the number of states (`Product(needs[i] + 1)`), `m` is the number of special offers, and `n` is the number of item types. While the theoretical worst-case is high, it's effective in practice for the given constraints.
Space
O(S * n), where `S` is the number of unique states (which is at most `Product(needs[i] + 1)`) and `n` is the number of item types. This space is primarily for the memoization table.
Trade-offs
Pros
Much more efficient than brute-force by eliminating redundant calculations.
Guarantees that the minimum cost for each subproblem is computed only once.
This is the standard and accepted solution for this problem given its constraints.
Cons
The space complexity can be large if the number of reachable states (distinct
needsvectors) is high.The theoretical worst-case time complexity is still high, although it performs well in practice for the given constraints.
Solutions
Solution
class Solution {public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) { int ans = total(price, needs); List<Integer> t = new ArrayList<>(); for (List<Integer> offer : special) { t.clear(); for (int j = 0; j < needs.size(); ++j) { if (offer.get(j) > needs.get(j)) { t.clear(); break; } t.add(needs.get(j) - offer.get(j)); } if (!t.isEmpty()) { ans = Math.min(ans, offer.get(offer.size() - 1) + shoppingOffers(price, special, t)); } } return ans; }private int total(List<Integer> price, List<Integer> needs) { int s = 0; for (int i = 0; i < price.size(); ++i) { s += price.get(i) * needs.get(i); } return s; }}class Solution {public: int shoppingOffers(vector<int> &price, vector<vector<int>> &special, vector<int> &needs) { int ans = total(price, needs); vector<int> t; for (auto &offer : special) { t.clear(); for (int j = 0; j < needs.size(); ++j) { if (offer[j] > needs[j]) { t.clear(); break; } t.push_back(needs[j] - offer[j]); } if (!t.empty()) ans = min(ans, offer[offer.size() - 1] + shoppingOffers(price, special, t)); } return ans; } int total(vector<int> &price, vector<int> &needs) { int s = 0; for (int i = 0; i < price.size(); ++i) s += price[i] * needs[i]; return s; }};class Solution: def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int: def total(price, needs): return sum(price[i] * needs[i] for i in range(len(needs))) ans = total(price, needs) t = [] for offer in special: t . clear() for j in range(len(needs)): if offer[j] > needs[j]: t . clear() break t . append(needs[j] - offer[j]) if t: ans = min(ans, offer[- 1] + self . shoppingOffers(price, special, t)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.