Closest Dessert Cost — Solution in Python, Java & C++
Closest Dessert Cost solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Closest Dessert Cost is a medium coding problem on arrays, dynamic programming and backtracking, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Backtracking
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A dessert is built from exactly one ice-cream base and any toppings. baseCosts[i] is the price of base i; toppingCosts[j] is the price of one portion of topping j. Each topping may be added zero, one or two times.
The cost of a dessert is the base price plus the price of all topping portions on it. Return the dessert cost closest to target; if two costs are equally close, return the lower one.
Example 1
Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10
Output: 10
Explanation: Base 7 plus one portion of topping 0 (3).
Example 2
Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9
Output: 8
Explanation: Both 8 and 10 are 1 away; the lower wins. 9 itself cannot be made.
Example 3
Input: baseCosts = [5], toppingCosts = [3], target = 12
Output: 11
Constraints
n == baseCosts.lengthm == toppingCosts.length1 <= n, m <= 101 <= baseCosts[i], toppingCosts[j] <= 10^41 <= target <= 10^4
Hints for Closest Dessert Cost
Hint 1
With at most 10 toppings and 3 choices each, there are only 3^10 = 59,049 topping combinations.
Hint 2
Enumerate every combination for every base (DFS over toppings, choosing 0, 1 or 2 portions), and keep the best cost under the tie rule.
Hint 3
Once a partial cost reaches
target, adding more toppings can only move it further away — prune that branch.
How to solve Closest Dessert Cost
The search space is tiny: n · 3^m ≤ 590,490 desserts. Enumerate them with a depth-first search, comparing each cost by distance to target and then by value.
Approach
- Keep
best, initialised to any valid cost (for example the first base alone). - For each base, run
dfs(i, cost): ifcost >= targetori == m, comparecostwithbestand stop; otherwise recurse with 0, 1 and 2 portions of toppingi. - Comparison:
costreplacesbestif|cost - target| < |best - target|, or the distances tie andcost < best. - Return
best.
Why it works
Every dessert is reached by exactly one path of choices, so the minimum over all leaves is the answer. The prune is safe: from a cost c >= target, any extension c' >= c is at least as far from target and not lower, so it can never beat c under the comparison.
Complexity
- Time —
O(n · 3^m) - Space —
O(m) recursion depth
Pitfalls
- Exactly one base is required — a dessert of toppings only is not allowed.
- Ties go to the cheaper dessert, not the first one found.
- Each topping may be used at most twice, so this is not an unbounded knapsack.
Reference solution
Python
from typing import List
def closestCost(baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
sums = {0}
for t in toppingCosts:
sums = {s + k * t for s in sums for k in range(3)}
best = baseCosts[0]
for b in baseCosts:
for s in sums:
c = b + s
d, bd = abs(c - target), abs(best - target)
if d < bd or (d == bd and c < best):
best = c
return bestJava
static int dessertBest;
static void dessertDfs(int[] tops, int i, int cost, int target) {
if (cost >= target || i == tops.length) {
int d = Math.abs(cost - target), bd = Math.abs(dessertBest - target);
if (d < bd || (d == bd && cost < dessertBest)) dessertBest = cost;
return;
}
dessertDfs(tops, i + 1, cost, target);
dessertDfs(tops, i + 1, cost + tops[i], target);
dessertDfs(tops, i + 1, cost + 2 * tops[i], target);
}
public static int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
dessertBest = baseCosts[0];
for (int b : baseCosts) dessertDfs(toppingCosts, 0, b, target);
return dessertBest;
}C++
void dessertDfs(const vector<int>& tops, int i, int cost, int target, int& best) {
if (cost >= target || i == (int) tops.size()) {
int d = abs(cost - target), bd = abs(best - target);
if (d < bd || (d == bd && cost < best)) best = cost;
return;
}
dessertDfs(tops, i + 1, cost, target, best);
dessertDfs(tops, i + 1, cost + tops[i], target, best);
dessertDfs(tops, i + 1, cost + 2 * tops[i], target, best);
}
int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
int best = baseCosts[0];
for (int b : baseCosts) dessertDfs(toppingCosts, 0, b, target, best);
return best;
}JavaScript
var closestCost = function(baseCosts, toppingCosts, target) {
var m = toppingCosts.length;
var best = baseCosts[0];
var consider = function(c) {
var d = Math.abs(c - target), bd = Math.abs(best - target);
if (d < bd || (d === bd && c < best)) best = c;
};
var dfs = function(i, cost) {
if (cost >= target || i === m) { consider(cost); return; }
dfs(i + 1, cost);
dfs(i + 1, cost + toppingCosts[i]);
dfs(i + 1, cost + 2 * toppingCosts[i]);
};
for (var b = 0; b < baseCosts.length; b++) dfs(0, baseCosts[b]);
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming