Shopping Offers

Medium

Asked by:

+1

16 views

Topics:

ArraysDynamic ProgrammingRecursion

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 i^th item, and an integer array needs where needs[i] is the number of pieces of the i^th 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 j^th item in the i^th offer and special[i][n] (i.e., the last integer in the array) is the price of the i^th 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.length
1 <= n <= 6
0 <= price[i], needs[i] <= 10
1 <= special.length <= 100
special[i].length == n + 1
0 <= special[i][j] <= 50
The input is generated that at least one of special[i][j] is non-zero for 0 <= j <= n - 1.

Shopping Offers

Medium

Asked by:

16 views

Topics:

ArraysDynamic ProgrammingRecursion

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 i^th item, and an integer array needs where needs[i] is the number of pieces of the i^th 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 j^th item in the i^th offer and special[i][n] (i.e., the last integer in the array) is the price of the i^th 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.length
1 <= n <= 6
0 <= price[i], needs[i] <= 10
1 <= special.length <= 100
special[i].length == n + 1
0 <= special[i][j] <= 50
The input is generated that at least one of special[i][j] is non-zero for 0 <= j <= n - 1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum values for the prices of individual items and the special offer prices?
Can the quantity of an item needed in a special offer be zero?
Can the quantity of an item needed from the shopping list be zero?
If no combination of special offers and individual items can fulfill the shopping list, what value should be returned?
Are the special offers mutually exclusive, or can multiple offers be applied to the same shopping list simultaneously?

Brute Force Solution

Approach

The brute force approach for the shopping offers problem means we're going to try every single possible combination of buying items, with and without the special offers. We'll keep track of the cost of each combination and ultimately pick the cheapest one.

Here's how the algorithm would work step-by-step:

Start by figuring out the cost of buying everything individually, without using any special offers.
Next, consider using a single special offer. Try each special offer, one at a time, and calculate the remaining items needed and their cost.
Then, try using two special offers together. Consider every possible pair of special offers, calculate remaining needs, and compute the total cost.
Keep doing this, adding one more special offer at a time, until you've considered using all of them together in every possible combination.
Each time you use special offers, make sure you still buy enough of each item to fulfill the original shopping list. If a special offer would cause you to buy less than needed, don't use that combination.
For each combination of special offers, calculate the total cost, which includes the cost of the special offers themselves, plus the cost of buying any remaining items individually.
Finally, compare the total cost of every single combination you've tried (including buying everything individually), and choose the combination with the lowest total cost.

Code Implementation

def shopping_offers_brute_force(price_list, special_offers, needs_list):
    minimum_cost = sum(price_list[i] * needs_list[i] for i in range(len(price_list)))

    def calculate_cost(current_needs, current_cost):
        nonlocal minimum_cost
        all_needs_met = all(need == 0 for need in current_needs)

        if all_needs_met:
            minimum_cost = min(minimum_cost, current_cost)
            return

        # Try buying remaining items individually
        individual_cost = sum(price_list[i] * current_needs[i] for i in range(len(price_list)))
        minimum_cost = min(minimum_cost, current_cost + individual_cost)

        # Iterate through each special offer.
        for offer in special_offers:
            valid_offer = True
            updated_needs = list(current_needs)

            # Check if offer can be applied
            for item_index, quantity in enumerate(offer[:-1]):
                if updated_needs[item_index] < quantity:
                    valid_offer = False
                    break

            if valid_offer:
                for item_index, quantity in enumerate(offer[:-1]):
                    updated_needs[item_index] -= quantity

                # Apply the offer recursively
                calculate_cost(updated_needs, current_cost + offer[-1])

    # Start with original needs and zero cost
    calculate_cost(needs_list, 0)

    return minimum_cost

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m * 2^n) – The brute force approach considers all possible combinations of the 'n' special offers. There are 2^n possible subsets of offers. For each of these subsets, we need to check if applying those offers fulfills the requirements of the 'm' items in the shopping list. If the offers don't satisfy the requirements, we calculate the remaining cost by iterating through the list of 'm' items, purchasing them individually. Thus, the time complexity is dominated by considering all possible subsets of the 'n' offers and then for each combination checking the cost for 'm' items, giving O(m * 2^n).

Space Complexity

O(K^S) – The dominant space complexity comes from the recursion stack. The depth of the recursion could be up to the number of special offers, S, as we try combinations of offers. At each level, we may need to store temporary copies of the shopping list to reflect the items remaining after applying the offers. In the worst case, we are potentially considering every combination of special offers, resulting in a branching factor related to the number of special offers, K. Therefore, the number of active branches and associated shopping lists stored could grow exponentially with respect to the number of special offers, leading to O(K^S) space complexity, where K is a factor based on the number of special offer branching at each node, and S is the number of special offers. Other variables and temporary storage for calculations consume negligible space compared to the recursion stack and intermediate shopping lists.

Optimal Solution

Approach

The best way to solve this is to think of it like making change. We want to use the special offers as much as possible before buying individual items. We'll explore different combinations of offers to find the cheapest way to buy everything on the shopping list.

Here's how the algorithm would work step-by-step:

Start with the shopping list of items we need to buy.
Check if we can fulfill the shopping list only by buying individual items, this will be our initial cheapest price.
Now, consider using the special offers. For each offer, check if we can use it to buy some of the items on our list.
If an offer can be used, imagine applying it to our shopping list. This means we subtract the items in the offer from our shopping list.
After applying an offer, we have a new shopping list. Recursively find the cheapest way to fulfill the new list, including using more special offers or buying individual items.
For each combination of offers we try, calculate the total cost (cost of the offers + the cheapest way to buy the remaining items).
Keep track of the lowest total cost we find across all the combinations we try.
The lowest total cost is the cheapest way to fulfill our original shopping list using the offers and individual items.

Code Implementation

def shopping_offers(price_list, special_offers, needs_list):
    def calculate_price(current_needs_list):
        total_price = 0
        for item_index, quantity in enumerate(current_needs_list):
            total_price += quantity * price_list[item_index]
        return total_price

    # Calculate cost without offers as base case
    min_price = calculate_price(needs_list)

    for offer in special_offers:
        # Create a copy to modify
        temp_needs_list = needs_list[:] 
        can_use_offer = True

        for item_index, quantity in enumerate(offer[:-1]):
            if quantity > temp_needs_list[item_index]:
                can_use_offer = False
                break

        if can_use_offer:
            # Apply the offer to the needs list
            for item_index, quantity in enumerate(offer[:-1]):
                temp_needs_list[item_index] -= quantity

            # Recursively find the minimum price with the updated needs
            min_price = min(min_price, offer[-1] + shopping_offers(price_list, special_offers, temp_needs_list))

    return min_price

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m^s) – The algorithm's time complexity is primarily driven by the recursion involved in exploring different combinations of special offers. In the worst case, we might need to consider all possible subsets of offers. Let m be the number of special offers and s be the size of the shopping list (number of items). Each level of the recursion corresponds to trying or not trying each offer. Since we explore combinations of offers until the shopping list is empty, in the worst-case scenario, where offers don't significantly reduce the shopping list, we may explore many combinations. Therefore, the time complexity grows exponentially with the number of offers, making it O(m^s) in the worst case where the offers are not effective in reducing the shopping list.

Space Complexity

O(D) – The dominant factor in space complexity is the recursion depth, where D is the maximum depth of the recursion tree. Each recursive call creates a new stack frame to store the modified shopping list. The depth of the recursion depends on how many offers can be applied sequentially before buying individual items. Therefore, the auxiliary space is proportional to the recursion depth, D, representing the maximum number of offers considered in a single path.

Edge Cases

Case	How to Handle
Empty price list	Return the cost of buying the items at regular price if there are no special offers.
Empty needs list	Return 0 as the cost because there are no items needed to buy.
Null or empty special offers list	Treat the situation like there are no special offers, so calculate based on regular prices only.
A special offer that requires more of an item than currently in the needs list	Reject the offer (don't use it) if the needs cannot fulfill the offer quantity.
A special offer leads to needing negative quantities of items	Reject the offer, as needing negative quantities doesn't make sense.
Integer overflow possible when calculating total cost	Use a larger integer type (e.g., long) for intermediate calculations to prevent overflow.
The 'needs' list contains an item not present in the 'price' list	Treat it as having a price of zero, or throw an IllegalArgumentException to indicate invalid input.
Maximum size of needs and special arrays cause memory issues (scalability)	Optimize the solution to reduce space complexity, possibly using iterative instead of recursive approaches.