1231. Divide Chocolate

HardArrayBinary Search
Leetcode Link

Problem Description

In this problem, you are given an array sweetness, where each element represents the sweetness level of a chunk of chocolate. You also have k friends with whom you want to share the chocolate. You plan to make k cuts to the chocolate bar, resulting in k + 1 pieces, each composed of consecutive chunks.

Your goal is to be generous with your friends and, therefore, you will choose the least sweet piece for yourself. However, you want to optimize this so that this least sweet piece is as sweet as possible. The task is to find the maximum sweetness you can get for your piece after making the k cuts in the best possible way.

Intuition

The solution leverages a binary search algorithm to find the optimal maximum sweetness you can achieve for your chocolate piece. The key insight is to realize that there is a range of possible sweetness levels for your piece – at the minimum, it could be the sweetness of the least sweet chunk, and at the maximum, it could be the total sweetness of the entire chocolate bar divided by k + 1.

The binary search approach gradually narrows down this range by guessing a potential maximum sweetness (mid), then checking if it's possible to cut the bar into k + 1 pieces where each piece has at least this level of sweetness. The check function is used to determine whether the current guess can be achieved by summing up the chunks' sweetness until it meets or exceeds the guessed level before making a cut. If the function can make more than k such valid cuts, the guess is feasible, and it means you might be able to increase the sweetness level for your piece, so you search in the higher half. Otherwise, the guess is too high, and you search in the lower half.

By repeatedly applying the binary search, you narrow down to the optimal l value, which represents the maximum sweetness you can achieve for your chocolate piece.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following array represent a max heap?

Solution Approach

The solution uses binary search to efficiently find the optimal cut points within the chocolate bar to maximize the sweetness of the piece you will eat. Below is the step-by-step explanation of the implementation:

  • First, we establish the search boundaries for binary search. The l (left boundary) is initialized to 0, assuming we cannot have a negative sweetness value, and r (right boundary) is initialized to the sum of all chunks' sweetness since this is the maximum sweetness we could potentially achieve if we didn't have to share with anyone.

  • We create a helper function check(x) with the parameter x representing the current guess for the maximum sweetness of the piece. It will return True if it is possible to cut the bar into more than k pieces where each piece has at least x sweetness. The function does this by iterating over the sweetness values, accumulating them until they reach or exceed x, then making a virtual cut and proceeding with the rest of the chunks.

  • Inside the while loop, which continues until l < r, we calculate the midpoint mid with (l + r + 1) >> 1. The operation >> 1 is equivalent to integer division by 2, so this finds the middle value between l and r. The +1 is important as it helps to avoid an infinite loop when l and r are close together.

  • The if condition inside the while loop uses the check(mid) function to decide which half of the current range to discard:

    • If check(mid) returns True, it means it's possible to cut the chocolate into pieces where each has at least mid sweetness. Therefore, we should try to find a potentially higher minimum sweetness, and we update l to mid.

    • If check(mid) returns False, it means mid is too high of a value for the minimum piece sweetness that we can assure for ourselves after doing the cuts. Thus, we update r to mid - 1.

  • The loop will exit when l equals r, which means we found the maximum sweetness that can still satisfy the conditions. The solution returns l, which is the optimal maximum sweetness we can achieve for our piece of chocolate.

This algorithm ensures we arrive at the ideal maximum minimum sweetness while making sure that the rest of the chocolate pieces are fair enough to be distributed to the k friends.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's go through an example to illustrate the solution approach. Suppose the sweetness array is [1, 2, 3, 4, 5, 6, 7, 8, 9], and you have k=2 friends.

Our goal is to find the maximum sweetness for the least sweet piece we can have after k cuts.

  1. We initialize l=0 and r=45 because 45 is the total sweetness (sum of all chunks) and the k+1 pieces implies that the maximum single piece's sweetness can't be more than 45/3=15.

  2. We create a helper function, check(x), which will go through the sweetness array, summing the values until it reaches or exceeds the current guess x, and then count a cut.

  3. Enter the binary search while-loop:

    • First iteration: l=0, r=45, so mid=(0+45+1) >> 1 = 23.

      • Check if it's possible to cut the bar so that each piece is at least 23 sweetness: No, because the highest sum we can get before the total sum exceeds 23 is 1+2+3+4+5+6=21, then 7+8+9=24, which only makes 1 cut. So, update r to mid - 1, which is 22.

    • Second iteration: l=0, r=22, so mid=(0+22+1) >> 1 = 11.

      • Check if it's possible with 11: Yes, one piece can be 1+2+3+4=10 (which is just under 11), the next can be 5+6=11, and the last piece will be 7+8+9=24 (far exceeding 11, but it's the last piece, so it's okay). We managed more than k cuts here, so update l to mid, which is 11.

    • Third iteration: l=11, r=22, so mid=(11+22+1) >> 1 = 17.

      • With 17, we can't reach the minimum sweetness before we've hit the end of the array (again, we get chunks like 1+2+3+4+5=15 and then 6+7+8+9=30), resulting in only 1 cut, so update r to mid - 1, which is 16.

    • Fourth iteration: l=11, r=16, so mid=(11+16+1) >> 1 = 14.

      • Attempt with 14: We can have the pieces 1+2+3+4+5=15 and 6+7=13 (below 14, so we keep adding) then 8+9=17, we're just making 2 cuts. Since we succeeded in making k cuts before the sum fell short of 14, we can continue searching between 14 to 16.

    • The process will continue, narrowing down the range until l equals r.

  4. By the end of the last iteration, when l equals r, we have found the right cut-off (mid) where we can still have more than k cuts with each piece being at least as sweet as our final value of l.

  5. The final value of l will be our answer. In this example, the maximum sweetness for the least sweet piece you can have would be 11 after iterating this process to the point where l and r converge.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
5        # Helper function to check if the minimum sweetness value 'min_sweetness'
6        # allows us to divide the chocolate into more than k+1 pieces
7        def can_divide(min_sweetness: int) -> bool:
8            total = 0
9            pieces = 0
10            # Go through each piece of the chocolate
11            for piece_sweetness in sweetness:
12                total += piece_sweetness
13                # If the total sweetness is at least 'min_sweetness',
14                # we can form a new piece
15                if total >= min_sweetness:
16                    total = 0
17                    pieces += 1
18            # The +1 is because we need to divide the chocolate into k+1 pieces
19            return pieces > k
20
21        # Initialize binary search bounds
22        # 'left' is the minimum possible sweetness, 'right' is the maximum possible sweetness
23        left, right = 1, sum(sweetness)
24        # Perform binary search to find the maximum minimum sweetness
25        while left < right:
26            # Calculate the middle point of the current search range
27            mid = (left + right + 1) // 2
28            # If we can divide the chocolate with 'mid' sweetness,
29            # we try to find a higher minimum sweetness value
30            if can_divide(mid):
31                left = mid
32            else:
33                # Otherwise, if we cannot, we look for a smaller minimum sweetness value
34                right = mid - 1
35        # Return the maximum minimum sweetness value we found
36        return left
37
1class Solution {
2    public int maximizeSweetness(int[] sweetness, int k) {
3        // Initialize the range of sweetness we will search within.
4        int left = 1; // The minimum sweetness can't be less than 1 (assuming sweetness array is positive).
5        int right = 0; // The maximum sweetness possible.
6
7        // Calculate the total sweetness in the array, which is the upper limit for binary search.
8        for (int sweet : sweetness) {
9            right += sweet;
10        }
11
12        // Perform a binary search to find the maximum sweetness that can be achieved.
13        while (left < right) {
14            // Use the mid point of the current range to test the sweetness level.
15            int mid = (left + right + 1) >>> 1;
16          
17            // Check if it's possible to have more than k pieces with at least 'mid' sweetness.
18            if (canSplit(sweetness, mid, k)) {
19                left = mid; // If possible, search towards the higher end of the range.
20            } else {
21                right = mid - 1; // Otherwise, search towards the lower end of the range.
22            }
23        }
24      
25        // Return the maximum sweetness level found.
26        return left;
27    }
28
29    private boolean canSplit(int[] sweetnessArray, int minimumSweetness, int k) {
30        int currentSum = 0; // Current piece sweetness sum.
31        int pieces = 0;     // Number of pieces formed.
32
33        // Sum up sweetness pieces and count how many are >= minimumSweetness.
34        for (int sweet : sweetnessArray) {
35            currentSum += sweet;
36            // When we reach the minimum sweetness for the current piece, increment piece count.
37            if (currentSum >= minimumSweetness) {
38                pieces++;
39                currentSum = 0; // Reset the sum for the next piece.
40            }
41        }
42      
43        // Check if we can have one more piece for the divider (k pieces means k+1 friends).
44        // Return true if pieces count is greater than k.
45        return pieces >= k + 1;
46    }
47}
48
1#include <vector>
2#include <numeric>
3
4class Solution {
5public:
6    // Function to maximize the minimum sweetness of the pieces divided
7    // Parameters:
8    // sweetness: vector of integers where each integer represents the sweetness of a piece
9    // k: number of friends to share the sweetness with (pieces to divide into k+1)
10    int maximizeSweetness(vector<int>& sweetness, int k) {
11        int left = 1; // minimum possible sweetness
12        int right = accumulate(sweetness.begin(), sweetness.end(), 0); // maximum possible sweetness
13      
14        // Helper lambda to check if a given minimum sweetness value is achievable
15        auto canAchieveSweetness = [&](int minSweetness) {
16            int currentSum = 0, cuts = 0;
17            for (int pieceSweetness : sweetness) {
18                currentSum += pieceSweetness;
19                if (currentSum >= minSweetness) {
20                    currentSum = 0;
21                    ++cuts; // Increase count of number of cuts/pieces
22                }
23            }
24            return cuts >= k + 1; // Check if we can make k+1 pieces
25        };
26      
27        // Binary search to find the maximum of the minimum sweetness that we can achieve
28        while (left < right) {
29            int mid = left + (right - left + 1) / 2; // Midpoint and to avoid integer overflow
30          
31            // If the current mid can achieve the minimum sweetness, search towards the higher end
32            if (canAchieveSweetness(mid)) {
33                left = mid;
34            } else {
35                right = mid - 1; // Otherwise, search towards the lower end
36            }
37        }
38      
39        // left will be the maximum of the minimum sweetness we can achieve
40        return left;
41    }
42};
43
1function maximizeSweetness(sweetness: number[], k: number): number {
2    let left = 0; // Initialize the lower bound of binary search
3    let right = sweetness.reduce((a, b) => a + b); // Initialize the upper bound as the sum of sweetness
4
5    // Define a helper function to check if it's possible to split the sweetness array
6    // into more than k parts where each part has a minimum total sweetness of x
7    const canSplit = (minimumSweetness: number): boolean => {
8        let currentSweetness = 0;
9        let partsCount = 0;
10        for (const value of sweetness) {
11            currentSweetness += value; // Add the sweetness value to the current sum
12            // If the current sum reaches the minimum sweetness threshold, we start a new part
13            if (currentSweetness >= minimumSweetness) {
14                currentSweetness = 0; // Reset the current sweetness for the next part
15                partsCount++; // Increment the count of parts
16            }
17        }
18        // Check if we can have more than k parts with the specified minimum sweetness
19        return partsCount > k;
20    };
21
22    // Use binary search to find the maximum minimum sweetness
23    while (left < right) {
24        const mid = (left + right + 1) >> 1; // Equivalent to Math.floor((left + right + 1) / 2)
25        // If it's possible to split into more than k parts with mid as minimum sweetness,
26        // it means we can try a higher minimum. So we update left to mid.
27        if (canSplit(mid)) {
28            left = mid;
29        } else {
30            // Otherwise, we need to look for a smaller minimum sweetness
31            right = mid - 1;
32        }
33    }
34    // After binary search, left will be the maximum minimum sweetness we can achieve
35    return left;
36}
37
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used in a depth first search?

Time and Space Complexity

The given Python code aims to maximize the sweetness of the piece a person can get after dividing the chocolate sweetness array into k + 1 pieces. It uses a binary search approach to find the solution.

Time Complexity

The binary search runs while l < r, which typically gives us a O(log n) complexity, where n is the range of values to be searched—in this case, the total sum of the sweetness array (sum(sweetness)).

Within each iteration of the binary search, the check function is called, which itself runs through the entire array once. Therefore, this part has a time complexity of O(m), where m is the length of the sweetness array.

Combining these two parts together, we get a total time complexity of O(m * log n) for the entire algorithm, taking into account the binary search and the linear scan in the check function for each mid value.

Space Complexity

The space complexity is O(1). No additional space is allocated that grows with the size of the input, as the variables l, r, mid, s, cnt, and x only use a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫