Meta / Amazon / Google Interview Question — LeetCode 1231

In this post, we are going to discuss leetcode 1231 — Divide Chocolate, which is asked in Google, Meta, and Amazon interviews.

Problem Analysis

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.

You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.

Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.

Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

Example 1:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5 
Output: 6 
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]

Example 2:

Input: sweetness = [5,6,7,8,9,1,2,3,4], k = 8 
Output: 1 
Explanation: There is only one way to cut the bar into 9 pieces.

Example 3:

Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2 
Output: 5 
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]

My Thinking Process

This is another type of problem, which seems to be very difficult and clueless at the first glance. However, this type of problem also follows a pattern, and there will be a common algorithm to solve it.

The key word in this problem is “ find the maximum of a minimum value “. For this type of problem, we will always use Binary Search to solve. The logic will be below:

1. Define the minimum possible value, which is simply the minimum value in the array.
2. Define the maximum possible value, which is the sum of the array and divided by the number of people. As I will always take the least sweetness, so the maximum sweetness I can take is when all the people share the same value of sweetness.

Then we have the boundary of min and max. And we can use Binary Search on the min and max, to find the maximum value we can get.

In every Binary Search loop, we just try to divide the chocolate. Once it is larger than or equal to the target value (which is the mid-value of the min and max), we can start the divide for the next person.

Code Implementation

Base on the analysis above, below is my implementation of the problem.