How hard is LeetCode 1231. Divide Chocolate?

LeetCode 1231. Divide Chocolate is rated Hard on LeetCode.

What is the time complexity of LeetCode 1231. Divide Chocolate?

The Python solution on this page runs in O(n \times \log \sum_{i=0}^{n-1} sweetness[i]).

What is the space complexity of LeetCode 1231. Divide Chocolate?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1231. Divide Chocolate cover?

LeetCode 1231. Divide Chocolate is tagged Array and Binary Search on LeetCode.

Is LeetCode 1231. Divide Chocolate a premium problem?

Yes. LeetCode 1231. Divide Chocolate is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Divide Chocolate — LeetCode 1231 Python Solution

HardLeetCode PremiumArrayBinary Search

Problem: #1231
Pattern: Monotonic Stack
Reading time: 3 min
Source: leetcode.com

The problem

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.

Example

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]

Python solution

Python

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def check(x: int) -> bool:
            s = cnt = 0
            for v in sweetness:
                s += v
                if s >= x:
                    s = 0
                    cnt += 1
            return cnt > k

        l, r = 0, sum(sweetness)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Complexity

Measure	Complexity
Time	O(n \times \log \sum_{i=0}^{n-1} sweetness[i])
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 1231. Divide Chocolate is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1231. Divide Chocolate?: LeetCode 1231. Divide Chocolate is rated Hard on LeetCode.
What is the time complexity of LeetCode 1231. Divide Chocolate?: The Python solution on this page runs in O(n \times \log \sum_{i=0}^{n-1} sweetness[i]).
What is the space complexity of LeetCode 1231. Divide Chocolate?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1231. Divide Chocolate cover?: LeetCode 1231. Divide Chocolate is tagged Array and Binary Search on LeetCode.
Is LeetCode 1231. Divide Chocolate a premium problem?: Yes. LeetCode 1231. Divide Chocolate is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.