638. Shopping Offers
Model: qwen3.5:9b
Topics: Dynamic Programming,Depth-first Search
FAANG asked: 1
Acceptance rate: 53.1%
Problem Breakdown
We are tasked with finding the minimum cost to purchase a specific set of item quantities (needs). We have two ways to acquire these items: buying them individually at their base price or using one of several available special offers. Each special offer specifies how many units of each item it provides and its total discounted price.
Inputs:
price: List of integers representing the individual cost for each distinct item type.special: A list of lists, where each inner list represents an offer (counts per item followed by the discount price).needs: The target quantity required for each item type.
Outputs:
- An integer representing the minimum total cost to satisfy exactly the requirements in
needs.
Constraints & Edge Cases:
- Exact Quantity Requirement: We cannot buy more items than specified in
needs(even if it’s cheaper). This means an offer is only valid if every item count within that offer current remaining need for that item. - State Space Size: Max 6 item types, max needs per type = 6. The state space defined by the tuple of
needsis relatively small (), making memoization viable. - Offer Reusability: Offers can be used multiple times as long as they fit within remaining needs.
Intuition
This problem asks for a minimum cost path to reach the state where all needs are zero (or satisfied). Since we want the minimum price, this suggests an optimization search over combinations of offers and individual items.
- Brute Force: We could try every permutation of using special offers until needs are met. However, since offers can be reused in any order or combination, without tracking visited states, we would recompute costs for the same remaining
needsvector multiple times (e.g., Offer A then B vs Offer B then A might lead to identical intermediate need vectors). This leads to exponential time complexity . - Key Insight: The problem exhibits optimal substructure and overlapping subproblems. If we reach a specific state of remaining
needsvia different paths, the minimum cost from that point forward is independent of how we got there. Therefore, this can be modeled as finding the shortest path in a Directed Acyclic Graph (DAG) where nodes are states defined by(n1, n2...). - Recursion with Memoization: We define a function
dfs(current_needs)that returns the min cost to satisfy those needs. To avoid recomputing for identical need vectors, we cache results using Dynamic Programming (Memoization).
Approach
We will use Depth-First Search (DFS) combined with memoization (@lru_cache). The algorithm proceeds as follows:
- Define Recursive Function:
dfs(needs)returns the minimum cost to satisfy the remaining items inneeds. - Base Case: If all values in
needsare zero, we have satisfied everything; return 0 (implicitly handled by calculating individual costs for empty needs). - Option A - Individual Items: Calculate the cost of buying every single unit required by
needsat their individual base prices. This serves as a fallback or baseline option if no special offer is beneficial for the remainder. - Option B - Special Offers: Iterate through each available special offer:
- Check validity: Ensure that applying this offer does not exceed any item count in
current_needs. (i.e.,offer_items[i] <= needs[i]for all i). - If valid, calculate the cost as
special_price + dfs(needs - offer_items).
- Check validity: Ensure that applying this offer does not exceed any item count in
- Combine: The result is the minimum of Option A and all valid results from Option B.
- Memoize: Store the computed min cost for each unique
needstuple before returning it to avoid redundant calculations in deeper recursion branches.
Complexity Analysis
- Time Complexity: , where is the number of special offers and is the size of the state space (number of valid need combinations). Given constraints (, ), the maximum distinct states for
needsis . With up to 100 offers, this fits well within time limits. - Space Complexity: for the memoization cache storing results for each unique state tuple of needs, plus recursion stack depth proportional to total items needed ().
Solution
from functools import lru_cache
from typing import List
class Solution:
def shoppingOffers(self, price: List[int], special: List[List[int]],
needs: List[int]) -> int:
@lru_cache(None)
def get_min_price(current_needs):
# Option A: Buy all remaining items at individual base prices.
# This is always a valid fallback path if no offers are used or fit better.
min_cost = sum(n * p for n, p in zip(current_needs, price))
# Try each special offer to see if it reduces the cost further
for items_in_offer_list in special:
# Check validity: Ensure we don't buy more than needed.
# Offer format is [item1_count, item2_count..., price]
valid = True
# Iterate through all item types present in needs (and offers)
for i in range(len(current_needs)):
if current_needs[i] < items_in_offer_list[i]:
valid = False
break
if valid:
new_needs_tuple = tuple(
n - o
for n, o in zip(current_needs, items_in_offer_list[:-1])
)
# Recurse with the reduced needs + price of this specific offer
cost_with_offer = get_min_price(new_needs_tuple) + items_in_offer_list[-1]
if cost_with_offer < min_cost:
min_cost = cost_with_offer
return min_cost
return get_min_price(tuple(needs))
Edge Cases Handled
- No Special Offers: The loop over
specialsimply doesn’t execute, returning the sum of individual prices. - Offer Exceeds Needs: Inside the offer iteration, we check if
current_needs[i] < items_in_offer_list[i]. If true for any item, that specific offer is skipped (valid = False). This strictly enforces “no overbuying”. - Individual Items Cheaper than Offer: The logic initializes
min_costwith the cost of buying individually. Even if an offer exists but costs more (or leaves a remainder that makes it expensive), the individual fallback ensures we don’t pick a suboptimal path. - Empty Needs List: If input is empty, sum returns 0 and loop doesn’t run; handled correctly by Python’s
sumon empty list returning 0.