LeetCode 638 - Shopping Offers

This problem asks us to find the minimum cost to buy a set of items given individual prices and optional special offers.

leetcodemediumarraydynamic-programmingbacktrackingbit-manipulationmemoizationbitmask

LeetCode Problem 638

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Memoization, Bitmask

Solution

Problem Understanding

This problem asks us to find the minimum cost to buy a set of items given individual prices and optional special offers. We are given three main inputs: an array price that specifies the unit price for each item, an array needs that specifies the exact number of each item we want to purchase, and a 2D array special that represents special offers. Each offer in special contains the quantities of items included and the total price of that offer.

The output is the lowest possible cost to satisfy the needs exactly, without buying extra items. This means we cannot overshoot any needs[i] even if that would reduce the overall price.

Key constraints give important hints about the problem’s scale. The number of items n is at most 6, and each need is at most 10. The number of special offers can be up to 100. Because n is small, we can consider solutions that involve exploring combinations of offers, but the total number of possible states grows exponentially with n and needs. The problem guarantees that every special offer includes at least one item, so no offer is empty.

Important edge cases include when needs are all zero (the cost is zero), when special offers are more expensive than buying items individually, or when an offer cannot be used without exceeding the need. The solution must handle these cases correctly.

Approaches

A brute-force approach is to try all combinations of special offers and individual purchases recursively. For each state defined by the current needs, we can either buy individual items or apply any special offer that does not exceed the remaining needs. This guarantees correctness because it explores every possibility, but it is extremely slow. The number of states is (needs[0]+1) * (needs[1]+1) * ... * (needs[n-1]+1), which is up to 11^6 ≈ 1.7 million states. Without memoization, repeated computations make this infeasible.

The key observation for an optimal solution is that the problem exhibits overlapping subproblems. For any given set of remaining needs, the minimum cost depends only on that state, so we can use memoization to store results and avoid recomputation. By treating the needs array as a tuple key in a hash map, we can efficiently cache results for each state and perform a recursive search with pruning.

Approach Time Complexity Space Complexity Notes
Brute Force O(choices^(n*max_need)) O(n*max_need) Explore all combinations of offers recursively without caching
Optimal O(11^n * m) O(11^n) Recursive backtracking with memoization, n items, m offers, each need ≤10

Algorithm Walkthrough

  1. Define a helper function dfs(needs) that computes the minimum cost for the current needs. This function will be called recursively.
  2. Base case: if all needs are zero, the cost is zero.
  3. Initialize min_cost as the cost of buying all remaining items at individual prices.
  4. Iterate over each special offer. Check if it can be applied without exceeding the current needs. If yes, compute a new needs array by subtracting the quantities in the offer.
  5. Recursively call dfs on the updated needs array and add the price of the current offer.
  6. Update min_cost if using this offer yields a lower total cost.
  7. Store the computed min_cost for the current needs in a memoization dictionary to avoid repeated calculations.
  8. Return the min_cost.

Why it works: At each state, we explore every valid combination of offers and individual purchases. Memoization guarantees that each unique state is computed only once, ensuring efficiency. Because we consider all valid options and pick the minimum, the solution is guaranteed to be correct.

Python Solution

from typing import List, Tuple

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        memo = {}
        
        def dfs(current_needs: Tuple[int, ...]) -> int:
            if current_needs in memo:
                return memo[current_needs]
            
            # Cost without any special offer
            min_cost = sum(current_needs[i] * price[i] for i in range(len(price)))
            
            # Try each special offer
            for offer in special:
                new_needs = []
                for i in range(len(price)):
                    if offer[i] > current_needs[i]:
                        break
                    new_needs.append(current_needs[i] - offer[i])
                else:
                    # Offer is valid, recurse
                    min_cost = min(min_cost, dfs(tuple(new_needs)) + offer[-1])
            
            memo[current_needs] = min_cost
            return min_cost
        
        return dfs(tuple(needs))

The Python implementation defines a memoized recursive function dfs to explore all valid combinations of special offers. For each recursive call, it first calculates the cost of buying remaining items individually, then tries each special offer that does not exceed the current needs. Valid offers update the needs, and the recursion continues. The memo dictionary stores results for each needs tuple, avoiding redundant computations.

Go Solution

func shoppingOffers(price []int, special [][]int, needs []int) int {
    memo := make(map[string]int)
    
    var dfs func([]int) int
    dfs = func(currentNeeds []int) int {
        key := fmt.Sprint(currentNeeds)
        if val, ok := memo[key]; ok {
            return val
        }
        
        minCost := 0
        for i, n := range currentNeeds {
            minCost += n * price[i]
        }
        
        for _, offer := range special {
            newNeeds := make([]int, len(currentNeeds))
            valid := true
            for i := range price {
                if offer[i] > currentNeeds[i] {
                    valid = false
                    break
                }
                newNeeds[i] = currentNeeds[i] - offer[i]
            }
            if valid {
                cost := dfs(newNeeds) + offer[len(offer)-1]
                if cost < minCost {
                    minCost = cost
                }
            }
        }
        
        memo[key] = minCost
        return minCost
    }
    
    return dfs(needs)
}

In Go, we use a map with string keys to memoize states, because slices cannot be directly used as map keys. Each state is converted to a string representation. The logic mirrors the Python solution: calculate base cost, iterate over valid offers, recurse on updated needs, and memoize the minimum cost.

Worked Examples

Example 1: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]

Step Current Needs Base Cost Offer Applied New Needs Total Cost
1 [3,2] 3_2 + 2_5 = 16 offer1 (3,0,5) [0,2] 5 + dfs([0,2]) = 5 + 10 = 15
2 [3,2] 16 offer2 (1,2,10) [2,0] 10 + dfs([2,0]) = 10 + 4 = 14
3 [3,2] min(16, 15, 14) - - 14

Final answer: 14

Example 2: price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]

Step Current Needs Base Cost Offer Applied New Needs Total Cost
1 [1,2,1] 2+6+4=12 offer1 [0,1,1] 4 + dfs([0,1,1]) = 4 + 7 = 11
2 [1,2,1] 12 offer2 invalid (needs < offer) -

Final answer: 11

Complexity Analysis

Measure Complexity Explanation
Time O(11^n * m) There are at most 11^n possible needs states, and for each state we try up to m offers
Space O(11^n) Memoization stores each state once, each state has size n

Because n ≤ 6 and needs[i] ≤ 10, 11^6 ≈ 1.7 million states is feasible. Memoization ensures we do not recompute states.

Test Cases

# Provided examples
assert Solution().shoppingOffers([2,5], [[3,0,5],[1,2,10]], [3,2]) == 14  # example 1
assert Solution().shoppingOffers([2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]) == 11  # example 2

# Edge cases
assert Solution().shoppingOffers([2,3], [], [1,1]) == 5  # no special offers
assert Solution