LeetCode 1231 - Divide Chocolate

The problem asks us to divide a chocolate bar into k + 1 consecutive pieces such that we maximize the minimum total sweetness among those pieces. Each element in the input array sweetness represents the sweetness of a single chunk.

leetcodehardarraybinary-search

LeetCode Problem 1231

Difficulty: 🔴 Hard
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks us to divide a chocolate bar into k + 1 consecutive pieces such that we maximize the minimum total sweetness among those pieces. Each element in the input array sweetness represents the sweetness of a single chunk. Our goal is to find an optimal way to make k cuts so that the smallest piece we get, when we eat the piece with the minimum sweetness, is as large as possible.

In other words, if we imagine sharing chocolate with k friends, we want the worst piece (the one we get) to be as good as possible. The output is a single integer representing the maximum possible total sweetness of the smallest piece we could get.

The constraints indicate that the array can be up to 10^4 in length, and each chunk can have sweetness up to 10^5. This rules out any brute-force solution that tries every possible cut, since that would be combinatorially explosive. Important edge cases include when k = 0 (we eat the whole chocolate) and when k = sweetness.length - 1 (every chunk becomes a piece). The problem guarantees all values are positive, so we do not have to handle zero or negative sweetness.

Approaches

A brute-force approach would involve trying every combination of k cuts and computing the minimum total sweetness among the resulting pieces. For each combination, we would keep track of the minimum piece and then take the maximum over all combinations. This is correct because it explicitly checks all possibilities, but it is infeasible due to the combinatorial explosion - for an array of length n and k cuts, the number of combinations is roughly C(n-1, k), which is astronomically large for n = 10^4.

The optimal approach leverages the key insight that this is a partition problem with monotonic property: if we can achieve a minimum sweetness of x per piece, we can also achieve any smaller value than x. This allows us to use binary search on the minimum sweetness value. For each candidate value mid, we simulate cutting the chocolate greedily, forming a new piece whenever the accumulated sweetness reaches or exceeds mid. If we can make at least k + 1 pieces this way, then mid is feasible; otherwise, it is too high. By adjusting the binary search boundaries based on feasibility, we find the maximum achievable minimum sweetness.

Approach Time Complexity Space Complexity Notes
Brute Force O(C(n-1, k) * n) O(n) Tries all possible k cuts explicitly, infeasible for large n
Optimal O(n log S) O(1) Binary search on minimum sweetness S with greedy validation

Here, S is the sum of all sweetness values in the array.

Algorithm Walkthrough

  1. Initialize the search space for binary search. Let left be the minimum possible piece sweetness, which is min(sweetness) or 1, and right be the maximum possible piece sweetness, which is sum(sweetness) // (k + 1) because we cannot get more than the total sweetness divided among all pieces.
  2. While left <= right, compute mid = (left + right) // 2. This represents a candidate minimum sweetness per piece.
  3. Simulate a greedy cut: iterate over the array, accumulating sweetness. When the running total reaches or exceeds mid, count it as a piece and reset the running total.
  4. After the iteration, check if we could make at least k + 1 pieces. If yes, it means mid is feasible, so move left to mid + 1 to search for a higher feasible value. If not, move right to mid - 1 to search for a smaller feasible value.
  5. Continue until the search space is exhausted. The largest feasible mid is the answer.

Why it works: the key invariant is that the feasibility of a minimum sweetness is monotonic: if a sweetness value is achievable, all smaller values are also achievable. This allows the binary search to converge on the maximum possible minimum sweetness efficiently.

Python Solution

from typing import List

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def can_divide(min_sweet: int) -> bool:
            count, curr_sum = 0, 0
            for s in sweetness:
                curr_sum += s
                if curr_sum >= min_sweet:
                    count += 1
                    curr_sum = 0
            return count >= k + 1

        left, right = min(sweetness), sum(sweetness) // (k + 1)
        answer = left

        while left <= right:
            mid = (left + right) // 2
            if can_divide(mid):
                answer = mid
                left = mid + 1
            else:
                right = mid - 1

        return answer

In the Python solution, we define a helper function can_divide that simulates cutting the chocolate greedily. We perform a binary search over possible minimum sweetness values. Each iteration updates left or right based on feasibility. The answer variable keeps track of the largest feasible minimum sweetness found so far.

Go Solution

func maximizeSweetness(sweetness []int, k int) int {
    canDivide := func(minSweet int) bool {
        count, currSum := 0, 0
        for _, s := range sweetness {
            currSum += s
            if currSum >= minSweet {
                count++
                currSum = 0
            }
        }
        return count >= k+1
    }

    left, right := 1, 0
    for _, s := range sweetness {
        right += s
    }
    right /= (k + 1)
    answer := 1

    for left <= right {
        mid := (left + right) / 2
        if canDivide(mid) {
            answer = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return answer
}

The Go solution mirrors the Python solution. We define an inline function canDivide for feasibility. Go requires handling integer division carefully and initializing right as the total sum divided by k + 1. The greedy logic for counting pieces is identical.

Worked Examples

Example 1: sweetness = [1,2,3,4,5,6,7,8,9], k = 5

Step mid Pieces formed left right answer
1 7 [1,2,3,4], [5], [6], [7], [8], [9] -> 6 pieces 7 22//6=3 6
2 6 6 pieces >= k+1 -> feasible left=6+1=7 right=6 answer=6

Final answer: 6

Example 2: sweetness = [5,6,7,8,9,1,2,3,4], k = 8

Binary search immediately finds that only 1-sweetness pieces are possible since k+1=9 pieces are needed. Final answer: 1

Example 3: sweetness = [1,2,2,1,2,2,1,2,2], k=2

mid Pieces formed
5 [1,2,2], [1,2,2], [1,2,2] -> 3 pieces
Final answer: 5

Complexity Analysis

Measure Complexity Explanation
Time O(n log S) Each binary search iteration takes O(n) for the greedy cut, and binary search has O(log S) iterations where S is sum(sweetness)
Space O(1) Only a few integers are stored; no extra arrays are needed

The binary search ensures efficiency, avoiding brute-force exploration of all possible cuts.

Test Cases

# Provided examples
assert Solution().maximizeSweetness([1,2,3,4,5,6,7,8,9], 5) == 6
assert Solution().maximizeSweetness([5,6,7,8,9,1,2,3,4], 8) == 1
assert Solution().maximizeSweetness([1,2,2,1,2,2,1,2,2], 2) == 5

# Edge cases
assert Solution().maximizeSweetness([1], 0) == 1  # Only one chunk, no cuts
assert Solution().maximizeSweetness([1,2,3,4,5], 4) == 1  # Each chunk becomes a piece
assert Solution().maximizeSweetness([10,10,10,10], 1) == 20  # Two pieces, maximize minimum

# Larger array
assert Solution().maximizeSweetness(list(range(1, 1001)), 9) == 495  # Sum 1..1000 = 500500, 10 pieces
Test Why
Single element, no cuts Handles minimum input, ensures