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)$$