HardBinary SearchArrayGreedy

Divide Chocolate

1 approach, code in every language

You have a chocolate bar described by an array where each value is the sweetness of one consecutive chunk. You want to share it with k friends, so you make k straight cuts between chunks, producing k + 1 contiguous pieces. Every piece keeps its chunks together, and the sweetness of a piece is the sum of the chunks inside it.

Being generous, you always take the piece with the least total sweetness. Choose the cuts so that this smallest piece is as sweet as possible, and return that maximum achievable minimum sweetness.

Example 1

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

Output: 6

Cutting into pieces [1,2,3], [4,5], [6], [7], [8], [9] gives sweetness 6, 9, 6, 7, 8, 9. The weakest piece is 6, and no set of six pieces can raise that floor higher.

Example 2

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

Output: 1

With 8 cuts every chunk becomes its own piece, so the smallest piece is simply the smallest chunk, which is 1.

Constraints

0 <= k < sweetness.length <= 10^4
1 <= sweetness[i] <= 10^5

Binary Search on the Minimum Piece

Binary search the target for the smallest piece; a greedy scan checks whether that target can yield at least k + 1 pieces.

Loading animation…

Intuition

Guessing a target sweetness x for the weakest piece has a monotonic structure: if you can carve out k + 1 pieces each worth at least x, then any smaller target is also achievable. That lets us binary search on x. The feasibility test is greedy: walk left to right accumulating sweetness, and every time the running total reaches x, seal a piece and reset. If the greedy scan produces enough pieces, the target is reachable, so we push for a higher target; otherwise we lower it.

Algorithm walkthrough

1Set lo to the smallest chunk and hi to the total sweetness divided by (k + 1), the best a minimum piece could ever be.
2Choose the upper mid of the window as the candidate minimum sweetness x.
3Greedily accumulate chunks; whenever the running sum reaches x, count a completed piece and reset the sum.
4If the count of completed pieces is at least k + 1, the target is feasible, so raise lo to mid; otherwise lower hi to mid - 1.
5When the window collapses, lo holds the maximum achievable minimum sweetness.

Implementation

from typing import List

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def can_cut(x: int) -> bool:
            pieces = cur = 0
            for s in sweetness:
                cur += s
                if cur >= x:
                    pieces += 1
                    cur = 0
            return pieces >= k + 1
        lo, hi = min(sweetness), sum(sweetness) // (k + 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if can_cut(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

Time

O(n log S), where n is the number of chunks and S is the total sweetness

Space

O(1)

Each feasibility check is a single linear pass; the number of checks is logarithmic in the total sweetness.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free