Divide Chocolate - Solution & Explanation
Problem Statement
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] <= 105
Approach Overview
Problem 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.
Solution
We notice that if we can eat a piece of chocolate with sweetness x, then we can also eat all chocolates with sweetness less than or equal to x. This shows monotonicity, therefore, we can use binary search to find the maximum x that satisfies the condition.
We define the left boundary of the binary search as l=0, and the right boundary as r=sum_{i=0}^{n-1} sweetness[i]. Each time, we take the middle value mid of l and r, and then determine whether we can eat a piece of chocolate with sweetness mid. If we can, then we try to eat a piece of chocolate with greater sweetness, i.e., let l=mid; otherwise, we try to eat a piece of chocolate with smaller sweetness, i.e., let r=mid-1. After the binary search ends, we return l.
The key to the problem is how to determine whether we can eat a piece of chocolate with sweetness x. We can use a greedy approach, traverse the array from left to right, accumulate the current sweetness each time, when the accumulated sweetness is greater than or equal to x, the chocolate count cnt is increased by 1, and the accumulated sweetness is reset to zero. Finally, check whether cnt is greater than k.
The time complexity is O(n times log sum_{i=0}^{n-1} sweetness[i]), and the space complexity is O(1). Where n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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 |
Video Solution
Google Coding Question - Divide Chocolate (LeetCode) • AlgosWithMichael • 13,453 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Divide Chocolate easy or hard?
Divide Chocolate Python/Java solution
How to solve Divide Chocolate in O(n)?
What is the best approach for Divide Chocolate?
Is Divide Chocolate asked at Google/Amazon/Meta?
What data structure is used in Divide Chocolate?
What is the time complexity of Divide Chocolate?
Ready to solve this problem?
Practice Divide Chocolate with our built-in code editor and test cases.
Practice on FleetCode