BS on Answer — Divide Chocolate

↗ LeetCode: Divide Chocolate · Hard · pattern chapter →

Asked atGoogleAmazon

Divide sweetness[] into k+1 contiguous pieces (you take the piece with the smallest sum). Maximize your piece's sweetness.

Example 1 — sweetness=[1,2,3,4,5,6,7,8,9], k=5 → 6Example 2 — sweetness=[5,6,7,8,9,1,2,3,4], k=8 → 1 (9 pieces, 1 each — you take min = 1) Example 3 — sweetness=[1,2,2,1,2,2,1,2,2], k=2 → 5 (3 pieces of sums [5, 5, 5])

Constraints — 1 ≤ k+1 ≤ n ≤ 10⁴; 1 ≤ sweetness[i] ≤ 10⁵. Answer range [1, 10⁹]. Brute enumeration of C(n,k) cuts is impossibly large; BS-on-answer is O(n log range) ≈ 3·10⁵ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute force: try every partition

Intuition. For each of the C(n-1, k) ways to place k cuts among n-1 gaps, compute the minimum piece sum, keep the max.

int maximizeSweetnessBrute(int[] a, int k) {
    return tryPartition(a, k, 0, 0);
}
int tryPartition(int[] a, int k, int start, int cutsPlaced) {
    if (cutsPlaced == k) return sumRange(a, start, a.length - 1);
    int best = 0;
    for (int end = start; end < a.length - (k - cutsPlaced); end++) {
        int firstPiece = sumRange(a, start, end);
        int rest = tryPartition(a, k, end + 1, cutsPlaced + 1);
        best = Math.max(best, Math.min(firstPiece, rest));
    }
    return best;
}

Complexity — Time O(C(n-1, k)) which blows up; Space O(k) recursion. For n=100, k=50, C(99,50) ≈ 10²⁹. In an interview state this then flip to binary search on the answer.

---

Approach 2 — Binary search on the minimum (canonical)

Insight. feasible(cap) = can we cut into ≥ k+1 pieces each with sum ≥ cap? Monotone — bigger cap → fewer possible cuts → harder. Find the largest cap where feasible(cap) still holds.

Range: lo = min(sweetness) (a piece must contain at least one item), hi = sum(sweetness) (one giant piece).

int maximizeSweetness(int[] sweetness, int k) {
    int lo = Integer.MAX_VALUE, hi = 0;
    for (int x : sweetness) { lo = Math.min(lo, x); hi += x; }
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;                     // upper mid for max-answer BS
        int cuts = 0, sum = 0;
        for (int x : sweetness) {
            sum += x;
            if (sum >= mid) { cuts++; sum = 0; }
        }
        if (cuts >= k + 1) lo = mid;                          // feasible → try larger
        else               hi = mid - 1;
    }
    return lo;
}

Execution Trace

BS on min — sweetness=[1..9], k=5 (6 pieces)

Step 1 / 6min 23 → only 1 piece → too big → hi=22

Complexity — Time O(n log sum); Space O(1). Say aloud in an interview: "for maximize-feasible, use the upper mid (lo + (hi - lo + 1) / 2) to avoid infinite loops. For minimize-feasible, use lower mid."

Try it yourself

Complexity summary

Approach	Time	Space
Brute enumeration	O(C(n-1, k))	O(k)
BS on min	O(n log sum)	O(1)

Watch the mid formula. For maximize-feasible BS, use lo + (hi - lo + 1) / 2 (upper mid) to avoid infinite loops.

When to use which

• "Max feasible X with monotone predicate" → BS on answer with ≥ target check.
• Return the splits → re-simulate after convergence.
• Bounded values → tight [lo, hi] speeds up.

✨AI Study CompanionBeta

Related problems

• Split Array Largest Sum — minimize the maximum (sibling)
• Koko Eating Bananas
• Minimize Max Distance to Gas Station

Was this page helpful?