Hard

Divide Chocolate

LAB

Split sweetness into k+1 contiguous pieces and maximize the minimum piece sweetness you get.

EXAMPLES

Example 1

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

Output
6

FUNCTION SHAPE

sweetness: intArrayk: int→int

SOLUTION NOTE

Max template. Opposite of Q410 - this is MAX of the MIN. Greedy check: can we make k+1 pieces each with sum >= mid?

Reveal reference solution +

pythonREFERENCE

def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
    def check(min_sweet):
        pieces, curr = 0, 0
        for s in sweetness:
            curr += s
            if curr >= min_sweet:
                pieces += 1
                curr = 0
        return pieces >= k + 1

    left, right = 1, sum(sweetness)
    while left < right:
        mid = ceil(left + (right - left) / 2)
        if check(mid):
            left = mid
        else:
            right = mid - 1
    return left

TimeO(n log(sum(sweetness)))

SpaceO(1)

Open on LeetCode ↗