⚡Flashcard Drill➔
NeetCode #270LC-1231HardBinary SearchNC Algo100
← Back to All Problems

#270 · #1231 · Divide Chocolate(分享巧克力)

📌 Problem Statement & Constraints

You have one chocolate bar with pieces of sweetness sweetness[i]. You will share it with k friends, so you cut the bar into k + 1 pieces, each a contiguous segment. You keep the piece with the minimum total sweetness. Return the maximum sweetness you can keep. Constraints: 1 <= k < sweetness.length <= 10^4, 1 <= sweetness[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Binary search on the answer: the predicate "can we make at least k + 1 pieces each with sweetness at least c" is monotone in c.
  2. The upper bound is sum(sweetness) / (k + 1), since the pieces must average at most that.
  3. For a given c, greedily cut whenever the running sum reaches c, and count the pieces.
  4. Feasible when the count is at least k + 1. Use the upper-biased midpoint since we want the maximum feasible value.

💻 Benchmark Python3 Implementation

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        lo, hi = 1, sum(sweetness) // (k + 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2   # upper-biased: maximise
            pieces = 0
            cur = 0
            for s in sweetness:
                cur += s
                if cur >= mid:
                    pieces += 1
                    cur = 0
            if pieces >= k + 1:
                lo = mid               # feasible -> try larger
            else:
                hi = mid - 1
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log(sum / k)): each predicate is O(n).
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using the lower-biased midpoint: with lo = mid on feasibility, the upper bias is required to avoid an infinite loop.
  • Requiring exactly k + 1 pieces: making more pieces is also fine, since they can be merged; the condition is >= k + 1.
  • Setting the upper bound to sum(sweetness): the average bound sum // (k + 1) is much tighter.
  • Sorting the pieces: the bar must be cut into contiguous segments, so the order is fixed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems