Watch 10 video solutions for Divide Chocolate, a hard level problem involving Array, Binary Search. This walkthrough by AlgosWithMichael has 13,229 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.
You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.
Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.
Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.
Example 1:
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5 Output: 6 Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]
Example 2:
Input: sweetness = [5,6,7,8,9,1,2,3,4], k = 8 Output: 1 Explanation: There is only one way to cut the bar into 9 pieces.
Example 3:
Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2 Output: 5 Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]
Constraints:
0 <= k < sweetness.length <= 1041 <= sweetness[i] <= 105Problem Overview: You are given an array where each element represents the sweetness of a chocolate chunk. You must cut the chocolate into k + 1 contiguous pieces and eat the piece with the minimum total sweetness. The goal is to maximize the sweetness of that minimum piece.
Approach 1: Brute Force Partitioning (Exponential Time, O(2^n) time, O(n) space)
The most direct idea is to try every possible combination of k cut positions and compute the sweetness of each resulting segment. For every partition, calculate the minimum segment sum and keep the maximum among those values. This requires exploring all subsets of cut positions, which grows exponentially with the array size. Even with prefix sums to speed up segment calculations, the search space is too large for practical input sizes.
Approach 2: Binary Search + Greedy (Optimal) (O(n log S) time, O(1) space)
The key observation: instead of deciding where to cut, search for the maximum possible minimum sweetness you can guarantee. This converts the problem into a decision question: can you create at least k + 1 pieces where each piece has sweetness ≥ X? Use binary search over the answer range from 1 to the total sweetness.
For a candidate value mid, scan the array greedily. Keep a running sum and form a piece whenever the accumulated sweetness reaches mid. Reset the sum and continue. If you can form at least k + 1 pieces, the candidate is feasible, so move the binary search right to try a larger minimum sweetness. Otherwise, move left.
This greedy validation works because splitting earlier always helps produce more segments. The monotonic property (larger minimum sweetness becomes harder to satisfy) makes the search space ideal for binary search. The array traversal is linear, so each feasibility check runs in O(n). Combined with the binary search range, the total complexity is O(n log S), where S is the sum of sweetness values.
The solution relies on iterating through an array and applying a greedy segment-building strategy during the feasibility check. Binary search narrows the answer space efficiently, avoiding explicit enumeration of cut positions.
Recommended for interviews: The Binary Search + Greedy approach is what interviewers expect. Recognizing that the objective function (minimum piece sweetness) can be searched with binary search demonstrates strong problem-solving skills. Mentioning the brute force idea shows you understand the search space, but implementing the greedy feasibility check proves you can optimize it effectively.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Partitioning | O(2^n) | O(n) | Conceptual baseline to understand all possible cut placements |
| Prefix Sum + DP Partitioning | O(n^2 * k) | O(n * k) | Useful when segment partition problems require exact DP optimization |
| Binary Search + Greedy | O(n log S) | O(1) | Optimal solution when the objective value is monotonic and can be validated greedily |