Closest Dessert Cost - Leetcode Solution

Problem statement:

You would like to buy dessert at a cafe that offers several kinds of desserts priced in whole dollars. You have dollar coins, and you want to spend all of them in a single transaction.

Given an array of integers prices where prices[i] is the price of the ith dessert in dollars, your task is to find the closest possible amount to target of a dessert that you can purchase with your coins. If there are multiple desserts that meet your criteria, you must choose the dessert with the minimum cost.

Return the index of the dessert you will purchase, or -1 if there is no such dessert.

Solution:

To solve this problem, we can follow the below approach:

1. Initialize a variable called “min_diff” to infinity and another variable called “closest” to -1.
2. Iterate through the prices array and for each element perform the below steps: a. Calculate the difference between the target and the current price and store it in a variable “diff”. b. If the “diff” is less than the current value of “min_diff” or if it is equal to the “min_diff” and the current price is less than the price of the dessert at the “closest” index, then update the values of “min_diff” and “closest” respectively.
3. If the value of “closest” is still -1, then return -1 as there is no such dessert that can be bought with the given coins.
4. Return the index of the dessert at the “closest” index.

Let's implement this in Python:

class Solution: def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int: min_diff = float('inf') closest = -1 for c in baseCosts: dfs(toppingCosts, target, c, min_diff, closest) return closest

def dfs(toppingCosts, target, curr_cost, min_diff, closest):
    if abs(target - curr_cost) < min_diff or (abs(target - curr_cost) == min_diff and curr_cost < closest):
        min_diff = abs(target - curr_cost)
        closest = curr_cost
    if closest == target:
        return
    if curr_cost > target:
        return
    for topping in toppingCosts:
        dfs(toppingCosts, target, curr_cost + topping, min_diff, closest)
        dfs(toppingCosts, target, curr_cost + 2 * topping, min_diff, closest)

Explanation:

In the given solution, we first initialize the variables “min_diff” and “closest” to infinity and -1 respectively. Then we loop through the “baseCosts” array, for each element we call the dfs function passing the “toppingCosts” array, the “target”, the current cost, the “min_diff”, and the “closest” variables. The dfs function performs the depth-first search to find the dessert closest to the target as described in the above approach. Finally, we return the “closest” variable.

The dfs function first checks whether the absolute value of the difference between the target and current cost is less than the “min_diff” or if it is equal to the “min_diff” and the current cost is less than the current value of “closest”. If it is true, then we update the “min_diff” and “closest” variables.

Next, we check whether the value of “closest” is equal to the target or if the current cost is greater than the target, then we return.

Otherwise, we loop through the elements in the “toppingCosts” array and call the dfs function recursively for each element in the array. We can add “topping” or “2 * topping” to the “curr_cost” variable depending on whether we want 1 or 2 toppings on the dessert.

Complexity Analysis:

The time complexity of this algorithm is O(2^(2*n)) where n represents the number of toppings as in the worst case scenario where all the toppings are used and there are two options for each topping. The space complexity is O(n) as the recursion depth can go up to n.

1