< Back




1231. Divide Chocolate

This is a pretty difficult problem because the initial approach / intuition required isn't obvious.
Initially, you're probably trying to figure out how to best segment the input into k + 1 subarrays,
which is a pretty daunting task.

Instead, we search for the minimum value that each chunk should be - we don't care if chunks are
greater. We'll split split the chocolate bar into chunks that meet or exceed this minimum value, and
check to make sure there are k + 1 chunks. If everyone gets a piece of chocolate, we know that the
minimum (m) and everything lower (m - 1 ... etc) are valid sweetness sums for a chunk of chocolate.
We need to binary search until we find the value m such that m + 1 is not a valid sweetness sum - we
won't be able to cut everyone a piece of chocolate. Then we'll know that m is the maximum sweetness
we can receive while satisfiying the constraint of cutting the chocolate into k + 1 pieces.

The solution is as follows:


  class Solution:
      def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
          l, r = min(sweetness), sum(sweetness) // (k + 1)

          while l < r:
              m, curr_sweetness, p = (r + l + 1) // 2, 0, 0

              for chunk in sweetness:
                  curr_sweetness += chunk

                  if curr_sweetness >= m:
                      p += 1
                      curr_sweetness = 0

              if p >= k + 1:
                  l = m
              else:
                  r = m - 1

          return r


_ Time Complexity:

  O(n log(s)) - Where s is the sum of the sweetness array and n is the length of the sweetness array.

_ Space Complexity:

  O(1) - We use constant space to retain our variables.