638. Shopping Offers


Problem Description

In this problem, we have a store on the LeetCode platform that has n items for sale. Each item has a price. Besides priced individually, there are also special offers that bundle one or more different kinds of items together for a sale price. The goal is to minimize the cost of buying a certain set of items by effectively utilizing these special offers.

To represent these items and offers, the problem provides us with:

  • An integer array price where price[i] represents the regular price of the ith item.
  • An integer array needs where needs[i] indicates the quantity of the ith item that we want to buy.
  • An array special where each special[i] is itself an array of size n + 1. The first n elements of special[i] indicate the number of each item included in the offer, and the last element (special[i][n]) represents the price of the offer.

We must calculate the lowest price required to purchase the exact items indicated by the needs array, using the special offers when they are cost-effective. It's important to note that we are not permitted to buy more items than needed just because it might reduce the total price.

Intuition

To find the solution, we will use a recursive approach to explore every possible combination of special offers and individual items. The intuition is that for each special offer, we either use it or don't in order to fulfill our needs. If the special offer has more items than we need, we discard it and move to the next offer. Otherwise, we subtract the offer's items from our needs and calculate the new total price.

The recursion works as follows:

  • Calculate the initial cost by summing the product of each item's individual price and the needed quantity.
  • Traverse each special offer and apply each valid one to see if it lowers the cost.
  • For each valid offer (an offer is valid if the quantity of each item in the offer does not exceed our needs):
    • Subtract the quantity of each item provided by the offer from our needs.
    • Recursively check whether using additional offers (including the same one again) starting from this new state would result in a lower total cost.
    • Compare this potential lower cost with our running minimum cost and retain the lower one.

By doing this, we consider all possible combinations of special offers and individual item prices, ensuring the minimum cost solution is found. The provided solution code uses memoization implicitly, as the recursive function calls itself with the reduced needs resulting from using an offer. Ultimately, the base case returns the direct cost without any special offers, and the recursive case tries to lower this cost by trying out different offer combinations.

Learn more about Memoization, Dynamic Programming, Backtracking and Bitmask patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The solution provided is a direct recursive implementation of the intuition previously discussed. In it, we are trying to find the minimum price to satisfy our needs by combining individual item costs and special offers. Here's how the solution is implemented:

  1. Recursive Helper Function - total: The helper function total takes the price array and a needs array to compute the total cost if only individual item prices are considered (no special offers).

  2. Base Case - Initial Cost: The base cost (without considering any special offers) is calculated by calling total(price, needs), which provides a reference for the minimum amount we would otherwise have to pay. This is stored in ans.

  3. Iteration Over Special Offers: The algorithm iterates over all the special offers in the special list and creates a temporary list, t, to hold the "remaining needs" after applying an offer.

  4. Check for Offer Validity: For each offer, the algorithm checks if it is valid; an offer is only valid if it does not exceed the current needs. If the offer is invalid, it is ignored.

  5. Application of Special Offers: For each valid offer, the algorithm calculates the remaining needs (t) after applying the offer by subtracting the offer quantities from the current needs.

  6. Recursive Call for Remaining Needs: If after applying an offer, there are still remaining needs (t is not empty), a recursive call to self.shoppingOffers is made to determine the minimum cost of satisfying these remaining needs. Importantly, the new total price after applying the offer is the sum of the cost of the special offer (offer[-1]) and the result of the recursive call.

  7. Minimization Step: The cost after each special offer application and subsequent recursive call is compared with the running minimum (ans). If the new total cost is lower, it updates ans, ensuring that we always have the lowest cost available.

  8. Memoization (Implicit): Even though the provided solution does not have explicit memoization, the recursion reuses calculations for the same needs states. It could be optimized by storing these intermediate results and avoiding repetitions of the same calculations.

  9. Return the Minimum Cost: Finally, the function returns ans, which represents the minimum cost after exploring the use of special offers.

The core algorithm makes clever use of recursion, enabling an exhaustive search while pruning infeasible paths by checking the validity of offers and not allowing the purchase of more items than needed. It compares the direct sum of the individual costs against the cost when using various combinations of special offers to ensure the best deal is found.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we have the following inputs for the store:

  • price = [2, 5] (The first item costs 2,andtheseconditemcosts2, and the second item costs 5)
  • special = [[1, 1, 5]] (There's one special offer where you can buy one unit of the first item and one unit of the second item for a total of $5)
  • needs = [3, 2] (We need to buy three units of the first item and two units of the second item)

We want to find the minimum cost to satisfy our needs.

Following the solution approach:

  1. Initial Cost Without Offers:

    • Using the total helper function (total(price, needs)), we calculate the initial cost without using any special offers. This would be 3 * $2 + 2 * $5 = $16. This value becomes our ans variable, which will store the running minimum cost.
  2. Iterate Over Special Offers:

    • We have one special offer to consider: [1, 1, 5].
  3. Check for Offer Validity and Apply Special Offers:

    • Check if using the special offer [1, 1, 5] does not exceed our needs [3, 2]. It does not, so we apply the offer. This leaves us with new needs of [2, 1] (subtracted one unit of each item from our original needs).
  4. Recursive Call for Remaining Needs:

    • With the new needs [2, 1], we make a recursive call to explore further possibilities of using the special offer or buying the remaining items at their regular price. We also account for the price of the offer we've just used, which was $5.
  5. Assuming the Initial Recursive Call:

    • Now we have a new state, [2, 1]. The offer can be applied once more without exceeding the needs, so we use the special offer again:
      • needs = [1, 0] (subtracting the offer from the previous needs)
      • Total cost so far would be 5(previousofferused)+5 (previous offer used) + 5 (current offer used) = $10.
    • Another recursive call is made with the new needs [1, 0].
  6. Recursive Call Cannot Use the Special Offer:

    • Now, the offer [1, 1, 5] cannot be used because it provides more of the second item than we need, which is 0. So we calculate the price for the remaining needs [1, 0] without the special offer, which is $2 (regular price for one unit of the first item).
    • The total cost up to this point would be 10(previoustotal)+10 (previous total) + 2 (regular price for the remaining items) = $12.
  7. Minimization Step:

    • We now compare the cost after using the special offer twice and buying one item at a regular price (12)withtheinitialcostwithoutusinganyspecialoffers(12) with the initial cost without using any special offers (16).
    • Since 12islower,weupdateansto12 is lower, we update `ans` to 12.
  8. Repeat the Process if There Are More Special Offers:

    • If there were more special offers, we would repeat the process for each one. However, in this example, there is only one special offer.
  9. Return the Minimum Cost:

    • Finally, after considering all possibilities, we find that the minimum cost obtainable is $12, which is the value of ans.
    • Hence, the function would return $12 as the minimum cost to satisfy the shopping needs [3, 2].

This walkthrough demonstrates the methodical recursive approach used to combine special offers with regular prices to find the minimum cost to meet the shopping needs, considering all feasible combinations and discount opportunities.

Not Sure What to Study? Take the 2-min Quiz:

Which technique can we use to find the middle of a linked list?

Python Solution

1from typing import List
2
3class Solution:
4    def shoppingOffers(self, prices: List[int], specials: List[List[int]], needs: List[int]) -> int:
5        # Helper function to calculate the total cost without any special offers
6        def calculate_total(prices: List[int], needs: List[int]) -> int:
7            return sum(prices[i] * needs[i] for i in range(len(needs)))
8
9        # Calculating the cost if no special offers are used
10        min_cost = calculate_total(prices, needs)
11      
12        # Iterate through each special offer
13        for special in specials:
14            # Initialize a temporary list for the updated needs after applying the special offer
15            updated_needs = []
16          
17            # Iterate through each item in the needs list to apply the special offer
18            for j in range(len(needs)):
19                # If the offer provides more than what is needed, ignore the offer
20                if special[j] > needs[j]:
21                    updated_needs = []
22                    break  # Break out of the loop as the offer is not applicable
23                # Update the remaining needs after applying the offer
24                updated_needs.append(needs[j] - special[j])
25          
26            # If the updated needs list is not empty, the offer is applicable
27            if updated_needs:
28                # Recursively calculate the minimum cost by using the special offer
29                # and update the minimum cost accordingly
30                min_cost = min(min_cost, special[-1] + self.shoppingOffers(prices, specials, updated_needs))
31      
32        # Return the minimum cost after checking all special offers
33        return min_cost
34

Java Solution

1class Solution {
2
3    // Calculates the minimum cost to satisfy shopping needs based on available
4    // individual item prices and special offers.
5    public int shoppingOffers(
6        List<Integer> prices, List<List<Integer>> specials, List<Integer> needs) {
7      
8        // Calculate the cost without any special offers
9        int minCost = calculateTotal(prices, needs);
10        List<Integer> newNeeds = new ArrayList<>();
11      
12        // Attempt to use each special offer to reduce the total cost
13        for (List<Integer> offer : specials) {
14            newNeeds.clear();
15
16            // Determine if the offer can be applied by checking if the needs
17            // are greater than or equal to what the offer provides
18            boolean validOffer = true;
19            for (int i = 0; i < needs.size(); ++i) {
20                if (offer.get(i) > needs.get(i)) {
21                    // If offer exceeds needs for any item, reject this offer
22                    validOffer = false;
23                    break;
24                }
25                // Calculate remaining needs after applying the offer
26                newNeeds.add(needs.get(i) - offer.get(i));
27            }
28
29            // If the offer is valid, recurse to find the minimum cost using 
30            // the reduced needs. The offer's price is added to this minimum cost
31            if (validOffer) {
32                minCost = Math.min(
33                    minCost,
34                    offer.get(offer.size() - 1) + shoppingOffers(prices, specials, newNeeds)
35                );
36            }
37        }
38        return minCost;
39    }
40
41    // Helper method to calculate the total cost without any special offers
42    private int calculateTotal(List<Integer> prices, List<Integer> needs) {
43        int totalCost = 0;
44        for (int i = 0; i < prices.size(); ++i) {
45            // Multiply the price of each item by the quantity needed
46            totalCost += prices.get(i) * needs.get(i);
47        }
48        return totalCost;
49    }
50}
51

C++ Solution

1class Solution {
2public:
3    // Function to calculate the minimum expense of shopping based on the item prices,
4    // special offers, and list of items needed.
5    int shoppingOffers(vector<int>& prices, vector<vector<int>>& specials, vector<int>& needs) {
6        // Calculate the total cost without any special offers.
7        int minCost = calculateTotal(prices, needs);
8        vector<int> remainingNeeds;
9      
10        // Go through each special offer to check if it can be applied
11        for (auto& offer : specials) {
12            remainingNeeds.clear();
13            bool offerApplicable = true;
14          
15            // Check if the offer can be applied by comparing each item's need against the offer.
16            for (int j = 0; j < needs.size(); ++j) {
17                // If the offer gives more than needed, it cannot be applied, so break the loop.
18                if (offer[j] > needs[j]) {
19                    offerApplicable = false;
20                    break;
21                }
22                // Track the remaining needs after applying the offer.
23                remainingNeeds.push_back(needs[j] - offer[j]);
24            }
25          
26            // If the offer is applicable, recursively calculate the new minimum cost
27            // with the remaining needs and update the minCost if it's lower.
28            if (offerApplicable)
29                minCost = min(minCost, offer.back() + shoppingOffers(prices, specials, remainingNeeds));
30        }
31        // Return the minimum cost found.
32        return minCost;
33    }
34
35    // Helper function to calculate the total cost of the items without any offers.
36    int calculateTotal(vector<int>& prices, vector<int>& needs) {
37        int sum = 0;
38        for (int i = 0; i < prices.size(); ++i)
39            sum += prices[i] * needs[i]; // Cost is price times quantity needed.
40        return sum;
41    }
42};
43

Typescript Solution

1// Function to calculate the minimum expense of shopping based on the item prices,
2// special offers, and the list of items needed.
3function shoppingOffers(prices: number[], specials: number[][], needs: number[]): number {
4    // Calculate the total cost without any special offers.
5    let minCost = calculateTotal(prices, needs);
6    let remainingNeeds: number[];
7
8    // Iterate through each special offer to check if it can be applied
9    for (const offer of specials) {
10        remainingNeeds = [];
11        let offerApplicable = true;
12
13        // Check if the offer can be applied by comparing each item's need against the offer.
14        for (let j = 0; j < needs.length; ++j) {
15            // If the offer gives more than needed, it cannot be applied, so break the loop.
16            if (offer[j] > needs[j]) {
17                offerApplicable = false;
18                break;
19            }
20            // Track the remaining needs after applying the offer.
21            remainingNeeds.push(needs[j] - offer[j]);
22        }
23
24        // If the offer is applicable, recursively calculate the new minimum cost
25        // with the remaining needs and update the minCost if it's lower.
26        if (offerApplicable)
27            minCost = Math.min(minCost, offer[offer.length - 1] + shoppingOffers(prices, specials, remainingNeeds));
28    }
29
30    // Return the minimum cost found.
31    return minCost;
32}
33
34// Helper function to calculate the total cost of the items without any offers.
35function calculateTotal(prices: number[], needs: number[]): number {
36    let sum = 0;
37    for (let i = 0; i < prices.length; ++i) {
38        // Cost is the price times the quantity needed for each item.
39        sum += prices[i] * needs[i];
40    }
41    return sum;
42}
43
Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

Time Complexity

The provided code snippet is a recursive function for solving a shopping offers problem, using special offers to find the minimum cost to satisfy certain shopping needs.

For each recursive call, we iterate over all the special offers. Let's denote S as the number of special offers and N as the number of items (or needs).

The function total computes the product of item prices and needs, performing N multiplications and additions, which takes O(N).

Within the for loop for each special offer, there is a nested loop iterating over the length of the needs, which takes O(N) per special offer. Inside this loop, we potentially make another recursive call to shoppingOffers.

A crucial aspect impacting time complexity is how deep the recursion goes (how many times the function calls itself), which depends on the size of special offers and if the special offer is usable (i.e., the offer does not exceed the remaining needs). Each recursive call can result in S more calls until the needs reduce to zero.

Therefore, in the worst case where we can always use a special offer (and thus needs decrement by at least 1), the maximum depth of the recursion tree would be product(needs), as at each level we reduce at least one item's need by at least 1.

The total time complexity would be O(S^product(needs) * N), since in the worst case for each recursive call, we loop over S offers and for each offer, we perform O(N) operations to calculate the remaining needs.

Space Complexity

The space complexity is determined by the maximum size of the call stack due to recursion and the space used to store temporary lists and parameters.

We have O(product(needs)) recursive calls in the call stack in the worst case since the depth of the recursion can be as much as the product of needs (in the case we reduce one unit per recursion per item).

Each recursive call uses a list t which can have at most N integers, plus the space used to store the parameters price, special, and needs. However, since lists are mutable and needs is modified in-place before the recursive call, each call stack frame directly holds O(N) for the list t and a constant amount of space for other arguments and local variables.

Thus, the space complexity due to the call stack and the temporary list is O(N * product(needs)).

It's important to note that product(needs) denotes the product of the quantities in the needs list, which represents the maximum number of recursive steps if each step reduces one quantity by one unit.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫