Divide Chocolate

Hard · Binary Search · Explanation and code example

Binary Search + Greedy

How it works

We want to maximize the minimum sweetness we receive after dividing the chocolate bar into k + 1 pieces. This is a classic binary search on the answer pattern. We binary search on possible sweetness values: for each candidate value mid, we greedily check if we can divide the bar so that at least k + 1 people each get a piece with sweetness at least mid. If we can, we try a higher value; if not, we try a lower one.

Steps

  1. Set the search range: left = min(sweetness) and right = sum(sweetness) / (k + 1).
  2. While left < right:
    • Compute mid = (left + right + 1) / 2.
    • Greedily assign consecutive chunks to people, cutting whenever the accumulated sweetness reaches mid.
    • Count how many people receive a piece with sweetness at least mid.
  3. If at least k + 1 people can receive such a piece, set left = mid.
  4. Otherwise, set right = mid - 1.
  5. Return right as the maximum possible minimum sweetness.

Complexity

  • Time complexity: O(n × log(S/(k + 1)))

    • The lower and upper bounds are min(sweetness) and S / (k + 1) respectively. In the worst case (when k is small), the right boundary will have the same magnitude as S, and the left boundary will be 1. Thus, the maximum possible time complexity for a single binary search is O(log S). For every single search, we need to traverse the chocolate bar in order to allocate chocolate chunks to everyone, which takes O(n) time.

  • Space complexity: O(1) constant space

Where n is the number of chunks in the chocolate, and S is the total sweetness of the chocolate bar.

Things to watch for

Off-by-One in Number of Pieces

The problem asks to divide chocolate among k + 1 people (yourself plus k friends). A common mistake is dividing into exactly k pieces instead of k + 1.

Using Wrong Binary Search Variant

This problem requires finding the maximum minimum value, which needs the "upper-bound" binary search variant. Using the standard lower-bound variant leads to incorrect results or infinite loops.

Incorrect Greedy Cutting Logic

When checking if a target sweetness is achievable, a common mistake is cutting as soon as accumulated sweetness equals the target, rather than when it reaches or exceeds the target. This fails when exact division is not possible.

Forgetting to Reset Accumulator After Cutting

After making a cut and counting a valid piece, forgetting to reset the sweetness accumulator causes incorrect counting of subsequent pieces.

Taking the First Valid Piece Instead of the Minimum

Since you get the piece with minimum sweetness and friends take theirs first, the greedy approach naturally gives you the last remaining piece. Some mistakenly try to track the minimum explicitly, which complicates the solution unnecessarily.

Python code example

from typing import List

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        # Initialize the left and right boundaries.
        # left = 1 and right = (total sweetness) / (number of people).
        number_of_people = k + 1
        left = min(sweetness)
        right = sum(sweetness) // number_of_people

        while left < right:
            # Get the middle index between left and right boundary indexes.
            # cur_sweetness stands for the total sweetness for the current person.
            # people_with_chocolate stands for the number of people that have
            # a piece of chocolate of sweetness greater than or equal to mid.
            mid = (left + right + 1) // 2
            cur_sweetness = 0
            people_with_chocolate = 0

            # Start assigning chunks to the current person.
            for s in sweetness:
                cur_sweetness += s

                # If the total sweetness is no less than mid, this means we can break off
                # the current piece and move on to assigning chunks to the next person.
                if cur_sweetness >= mid:
                    people_with_chocolate += 1
                    cur_sweetness = 0

            if people_with_chocolate >= k + 1:
                left = mid
            else:
                right = mid - 1

        return right

C++ code example

class Solution {
public:
    int maximizeSweetness(vector<int>& sweetness, int k) {
        // Initialize the left and right boundaries.
        // left = 1 and right = total sweetness / number of people.
        int numberOfPeople = k + 1;
        int left = *min_element(sweetness.begin(), sweetness.end());
        int right = accumulate(sweetness.begin(), sweetness.end(), 0) / numberOfPeople;

        while (left < right) {
            // Get the middle index between left and right boundary indexes.
            // cur_sweetness stands for the total sweetness for the current person.
            // people_with_chocolate stands for the number of people that have
            // a piece of chocolate of sweetness greater than or equal to mid.
            int mid = (left + right + 1) / 2;
            int curSweetness = 0;
            int peopleWithChocolate = 0;

            // Start assigning chunks to the current people,.
            for (int s : sweetness) {
                curSweetness += s;

                // When the total sweetness from him is no less than mid, meaning we
                // have done with him and move on to assigning chunks to the next people.
                if (curSweetness >= mid) {
                    peopleWithChocolate += 1;
                    curSweetness = 0;
                }
            }

            // Check if we successfully give everyone a piece of chocolate with sweetness
            // no less than mid, and eliminate the search space by half.
            if (peopleWithChocolate >= numberOfPeople) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        // Once the left and right boundaries coincide, we find the target value,
        // that is, the maximum possible sweetness we can get.
        return right;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations