Closest Dessert Cost

Medium
1483.

Closest Dessert Cost

Closest Dessert Cost is a medium coding problem on arrays, dynamic programming and backtracking, asked in Amazon and Google interviews.

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.length
  • m == toppingCosts.length
  • 1 <= n, m <= 10
  • 1 <= baseCosts[i], toppingCosts[j] <= 10^4
  • 1 <= target <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} baseCosts
 * @param {number[]} toppingCosts
 * @param {number} target
 * @return {number}
 */
var closestCost = function(baseCosts, toppingCosts, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • m == toppingCosts.length
  • 1 <= n, m <= 10
  • 1 <= baseCosts[i], toppingCosts[j] <= 10^4
  • 1 <= target <= 10^4

Hints for Closest Dessert Cost

  1. Hint 1

    With at most 10 toppings and 3 choices each, there are only 3^10 = 59,049 topping combinations.

  2. 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.

  3. 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

  1. Keep best, initialised to any valid cost (for example the first base alone).
  2. For each base, run dfs(i, cost): if cost >= target or i == m, compare cost with best and stop; otherwise recurse with 0, 1 and 2 portions of topping i.
  3. Comparison: cost replaces best if |cost - target| < |best - target|, or the distances tie and cost < best.
  4. 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 best

Java

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