Domain 2MediumCORE

Shopping Offers

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming#Depth-first Search

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:

  1. price: List of integers representing the individual cost for each distinct item type.
  2. special: A list of lists, where each inner list represents an offer (counts per item followed by the discount price).
  3. 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:

  1. 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 ≤\le current remaining need for that item.
  2. State Space Size: Max 6 item types, max needs per type = 6. The state space defined by the tuple of needs is relatively small (76≈117k7^6 \approx 117k), making memoization viable.
  3. 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.

  1. 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 needs vector 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 O(MN)O(M^N).
  2. Key Insight: The problem exhibits optimal substructure and overlapping subproblems. If we reach a specific state of remaining needs via 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...).
  3. 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:

  1. Define Recursive Function: dfs(needs) returns the minimum cost to satisfy the remaining items in needs.
  2. Base Case: If all values in needs are zero, we have satisfied everything; return 0 (implicitly handled by calculating individual costs for empty needs).
  3. Option A - Individual Items: Calculate the cost of buying every single unit required by needs at their individual base prices. This serves as a fallback or baseline option if no special offer is beneficial for the remainder.
  4. 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).
  5. Combine: The result is the minimum of Option A and all valid results from Option B.
  6. Memoize: Store the computed min cost for each unique needs tuple before returning it to avoid redundant calculations in deeper recursion branches.

Complexity Analysis

  • Time Complexity: O(M⋅S)O(M \cdot S), where MM is the number of special offers and SS is the size of the state space (number of valid need combinations). Given constraints (Nitems≤6N_{items} \le 6, needsi≤6needs_i \le 6), the maximum distinct states for needs is ∏(needi+1)=76\prod (need_i + 1) = 7^6. With up to 100 offers, this fits well within time limits.
  • Space Complexity: O(S)O(S) for the memoization cache storing results for each unique state tuple of needs, plus recursion stack depth proportional to total items needed (∑needi\sum need_i).

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 special simply 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_cost with 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 sum on empty list returning 0.