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
- Binary search on the answer: the predicate "can we make at least
k + 1pieces each with sweetness at leastc" is monotone inc. - The upper bound is
sum(sweetness) / (k + 1), since the pieces must average at most that. - For a given
c, greedily cut whenever the running sum reachesc, and count the pieces. - 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 = midon feasibility, the upper bias is required to avoid an infinite loop. - Requiring exactly
k + 1pieces: 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 boundsum // (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.