1231. Divide Chocolate

This page provides solutions for the leetcode problem 1231. Divide Chocolate.

Problem Explanation

The problem is asking us to divide a chocolate into $\text{K} + 1$ pieces such that you maximize the minimum total sweetness. Total sweetness here refers to the sum of elements of a subarray.

Solution

This problem can be solved using the Binary Search technique. More such questions can be found here.

Java

class Solution {
  public int maximizeSweetness(int[] sweetness, int k) {
    int lo = Integer.MAX_VALUE;
    int hi = 0;

    for(int i = 0; i < sweetness.length; i++) {
      lo = Math.min(lo, sweetness[i]);
      hi += sweetness[i];
    }

    k++;
    while(lo < hi) {
      int mid = (lo + hi + 1) / 2; 
      int partitions = getPartitions(sweetness, mid); 
      if (partitions < k) hi = mid - 1;
      else lo = mid;
    }
    return lo;
  }

  private int getPartitions(int[] nums, int required) {
    int index = 0, sum = 0, partitions = 0;
    while (index < nums.length) {
      sum += nums[index];
      if (sum >= required) {
        sum = 0;
        partitions++;
      }
      index++;
    }
    return partitions;
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array, and total sum of all elements in an array is $\text{S}$.

Time Complexity

The time complexity is $\text{O}(\log \text{S})$ for searching the optimal solution using binary search, and $\text{O}(\text{N})$ for checking if the array can be split into $\text{K}$ subarrays, so total time complexity will be:

$$\text{O}(\text{N} \log \text{S})$$

Space Complexity

The solution uses constant space for storing binary search variables, so total space complexity will be:

$$\text{O}(1)$$