1774. Closest Dessert Cost LeetCode Solution

In this guide, you will get 1774. Closest Dessert Cost LeetCode Solution with the best time and space complexity. The solution to Closest Dessert Cost problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Closest Dessert Cost solution in C++
Closest Dessert Cost solution in Java
Closest Dessert Cost solution in Python
Additional Resources

1774. Closest Dessert Cost LeetCode Solution image

Problem Statement of Closest Dessert Cost

You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:

There must be exactly one ice cream base.
You can add one or more types of topping or have no toppings at all.
There are at most two of each type of topping.

You are given three inputs:

baseCosts, an integer array of length n, where each baseCosts[i] represents the price of the ith ice cream base flavor.
toppingCosts, an integer array of length m, where each toppingCosts[i] is the price of one of the ith topping.
target, an integer representing your target price for dessert.

You want to make a dessert with a total cost as close to target as possible.
Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.

Example 1:

Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10
Output: 10
Explanation: Consider the following combination (all 0-indexed):
– Choose base 1: cost 7
– Take 1 of topping 0: cost 1 x 3 = 3
– Take 0 of topping 1: cost 0 x 4 = 0
Total: 7 + 3 + 0 = 10.

Example 2:

Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
Output: 17
Explanation: Consider the following combination (all 0-indexed):
– Choose base 1: cost 3
– Take 1 of topping 0: cost 1 x 4 = 4
– Take 2 of topping 1: cost 2 x 5 = 10
– Take 0 of topping 2: cost 0 x 100 = 0
Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.

Example 3:

Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9
Output: 8
Explanation: It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.

Constraints:

n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 104
1 <= target <= 104

Complexity Analysis

Time Complexity: O(n \cdot 3^m)
Space Complexity: O(n \cdot 3^m)

1774. Closest Dessert Cost LeetCode Solution in C++

class Solution {
 public:
  int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts,
                  int target) {
    int ans = INT_MAX;

    for (const int baseCost : baseCosts)
      dfs(toppingCosts, 0, target, baseCost, ans);

    return ans;
  }

 private:
  void dfs(const vector<int>& toppingCosts, int i, int target, int currCost,
           int& ans) {
    if (abs(currCost - target) < abs(ans - target))
      ans = currCost;
    if (i == toppingCosts.size() || currCost >= target)
      return;

    for (int k = 0; k < 3; ++k)
      dfs(toppingCosts, i + 1, target, currCost + k * toppingCosts[i], ans);
  }
};
/* code provided by PROGIEZ */

1774. Closest Dessert Cost LeetCode Solution in Java

class Solution {
  public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
    for (final int baseCost : baseCosts)
      dfs(toppingCosts, 0, target, baseCost);
    return ans;
  }

  private int ans = Integer.MAX_VALUE;

  private void dfs(int[] toppingCosts, int i, int target, int currCost) {
    if (Math.abs(currCost - target) < Math.abs(ans - target))
      ans = currCost;
    if (i == toppingCosts.length || currCost >= target)
      return;

    for (int k = 0; k < 3; ++k)
      dfs(toppingCosts, i + 1, target, currCost + k * toppingCosts[i]);
  }
}
// code provided by PROGIEZ