Problem Description

You are given an array sweetness of length n, where sweetness[i] represents the sweetness of the i-th chunk of chocolate. You want to split the chocolate into k + 1 pieces by making k cuts, such that each piece consists of consecutive chunks. Your goal is to maximize the minimum total sweetness among all the pieces after the split.

In other words, after dividing the chocolate into k + 1 pieces, you want the piece with the smallest total sweetness to be as large as possible.

Constraints:

• 1 <= k < n <= 10⁴
• 1 <= sweetness[i] <= 10⁹
• There is always at least one valid solution.
• You must not reuse any chocolate chunk in more than one piece.

Thought Process

At first glance, the problem seems to ask for all possible ways to split the chocolate and then pick the one where the smallest piece is as large as possible. Brute-forcing all possible cut positions would be extremely inefficient due to the exponential number of combinations.

However, by rephrasing the problem, we see that it's about maximizing the minimum sum of chunks in any piece after k cuts. This is a classic "maximize the minimum" problem, which can often be solved using binary search.

The key realization is that, for a given minimum sweetness value, we can check if it’s possible to make the required number of pieces. If it is, maybe we can do even better; if not, we need to lower our expectations.

Solution Approach

To solve this efficiently, we use a binary search approach combined with a greedy check:

1. Binary Search on Answer:
   • We search for the largest possible minimum sweetness value that allows us to split the chocolate into k + 1 pieces.
   • The search range is from min(sweetness) (the smallest possible piece) to sum(sweetness) // (k + 1) (the largest possible minimum sweetness).
2. Greedy Check (Feasibility):
   • For a candidate minimum sweetness value, iterate through the array, accumulating sweetness.
   • Each time the current sum reaches or exceeds the candidate, we "cut" and start a new piece.
   • Count how many pieces we can make this way. If we get at least k + 1 pieces, the candidate is feasible.
3. Binary Search Update:
   • If feasible, try higher values (move right); otherwise, try lower values (move left).

This approach ensures we find the largest minimum sweetness possible.

Example Walkthrough

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

1. Target: Split into k + 1 = 6 pieces, maximize the minimum sweetness.
2. Sum: 1+2+3+4+5+6+7+8+9 = 45
3. Possible minimum: 45 // 6 = 7
4. Start binary search between 1 and 7.
5. Try mid = 4:
   • Make cuts when sum >= 4: [1,2,3] (sum=6, cut), [4] (sum=4, cut), [5] (sum=5, cut), [6] (sum=6, cut), [7] (sum=7, cut), [8] (sum=8, cut), [9] (sum=9, cut)
   • We get more than 6 pieces, so 4 is feasible. Try higher.
6. Try mid = 6:
   • Make cuts when sum >= 6: [1,2,3] (sum=6, cut), [4,5] (sum=9, cut), [6] (sum=6, cut), [7] (sum=7, cut), [8] (sum=8, cut), [9] (sum=9, cut)
   • We get 6 pieces, so 6 is feasible. Try higher.
7. Try mid = 7:
   • Make cuts when sum >= 7: [1,2,3,4] (sum=10, cut), [5,6] (sum=11, cut), [7] (sum=7, cut), [8] (sum=8, cut), [9] (sum=9, cut)
   • We get 5 pieces only, so 7 is not feasible. Lower the target.
8. The answer is 6.

Time and Space Complexity

• Brute-force:
  • Would require checking all combinations of k cuts among n-1 positions: exponential in k (combinatorial explosion).
• Optimized (Binary Search):
  • Binary search runs in O(\log S) steps, where S is the sum of all sweetness.
  • Each check is O(n) (single pass through the array).
  • Total: O(n \log S).
  • Space complexity: O(1) extra space (in-place iteration).

Summary

The "Divide Chocolate" problem is a classic example of maximizing the minimum in a partitioning scenario. By recognizing the structure, we use binary search to efficiently home in on the optimal answer. The greedy check ensures we don't miss feasible splits, and the binary search guarantees we find the largest minimum sweetness possible. This approach is both elegant and efficient, making it suitable for large input sizes.

Code Implementation

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def can_divide(min_sweet):
            cuts = 0
            curr = 0
            for val in sweetness:
                curr += val
                if curr >= min_sweet:
                    cuts += 1
                    curr = 0
            return cuts >= k + 1

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

class Solution {
public:
    int maximizeSweetness(vector<int>& sweetness, int k) {
        auto can_divide = [&](int min_sweet) {
            int cuts = 0, curr = 0;
            for (int val : sweetness) {
                curr += val;
                if (curr >= min_sweet) {
                    cuts++;
                    curr = 0;
                }
            }
            return cuts >= k + 1;
        };
        int left = 1, right = accumulate(sweetness.begin(), sweetness.end(), 0) / (k + 1);
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (can_divide(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};
      

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int left = 1, right = 0;
        for (int s : sweetness) right += s;
        right /= (k + 1);

        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (canDivide(sweetness, k, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean canDivide(int[] sweetness, int k, int minSweet) {
        int cuts = 0, curr = 0;
        for (int val : sweetness) {
            curr += val;
            if (curr >= minSweet) {
                cuts++;
                curr = 0;
            }
        }
        return cuts >= k + 1;
    }
}
      

var maximizeSweetness = function(sweetness, k) {
    function canDivide(minSweet) {
        let cuts = 0, curr = 0;
        for (let val of sweetness) {
            curr += val;
            if (curr >= minSweet) {
                cuts++;
                curr = 0;
            }
        }
        return cuts >= k + 1;
    }
    let left = 1, right = Math.floor(sweetness.reduce((a, b) => a + b, 0) / (k + 1));
    while (left < right) {
        let mid = Math.floor((left + right + 1) / 2);
        if (canDivide(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
};