Cracking the Minimum Candy Distribution Problem
Problem Statement
There are N children standing in a line and each child is assigned a rating value. You are giving candies to these children while making sure that each child must have at least one candy and children with a higher rating get more candies than their neighbors. What is the minimum candies you must give?
Examples:
- Input: [1 ,0 , 2] | Output: 5 { Distribution: [2, 1, 2] }
- Input: [1, 2, 2] | Output: 4 { Distribution: [2, 1, 1] }
- Input: [0, 2, 0, 6, 6] | Output: 7 { Distribution:[1, 2, 1, 2, 1] }
Solution 🍬— Time & Space Complexity O(n)
Basically, every child has to evaluate both neighbors (previous child and next child) to find the candy count that he/she should get:
- If the child has a higher than the neighbor/s, then the child should get more candies than the neighbor/s.
- If the child has a lower than or equals to rating than the neighbor/s, then the neighbors/s can be ignored since this has no impact on the candy count of the child in question.
The concrete steps of the algorithm and it’s code is as follows:
- Forward Traversal: Start traversing the ratings from the first child and update the candy count of the next child on the way. If the rating of the current child is less than the next child’s rating, then the next child’s candy count must be at least 1 more than the candy count of the current child.
- Backward Traversal: Start traversing the ratings from the last child and update the candy count of the previous child on the way. If the rating of the current child is less than the previous child’s rating then the previous child’s candy count must be at least 1 more than the candy count of the current child.
- Count Candies: Calculate sum of the candy counts for each child for the final count.
// Language: Java
// Time Complexity: O(n) 3 Linear traversals.
// Space Complexity: O(n) Array of candies.public int candy(int[] ratings) {
if (ratings.length < 2) {
return ratings.length;
}
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
// ** Step 1: Forward **
for (int i=0; i<ratings.length-1; i++) {
if (ratings[i] >= ratings[i+1]) {
continue;
}
candies[i+1] = candies[i] + 1;
}
// ** Step 2: Backward **
for (int i=ratings.length-1; i>0; i--) {
if (ratings[i] >= ratings[i-1]) {
continue;
}
candies[i-1] = Math.max(candies[i] + 1, candies[i-1]);
}
// ** Step 3: Count Candies **
int count = 0;
for (int i=0; i<candies.length; i++) {
count += candies[i];
}
return count;
}
This is a perfectly acceptable solution, but we can save some space by optimizing the algorithm in the next section.
🍬 Optimization of Space — O(n) -> O(1)
Introduction of Basics
Let’s visualize the distribution of input [0, 4, 9, 25, 8, 6, 5] as follows:
Here are some important observations:
- 📈 Upward Slope (increasing numbers) for [0, 4, 9, 25] is of
length=4. - Candy count in the upward slope is 10=1+2+3+4 which is the sum of sequentially increasing numbers with n=length=4 (n*n+1/2)
- 📉 Downward Slope (decreasing numbers) for [25, 8, 6, 5] is of length=4.
- Candy count in the downward slope is 10=4+3+2+1 which is the sum of sequentially increasing numbers with n=length=4 (n*n+1/2)
- The Peak for both slopes is the middle child with rating 25.
Candy Count for Peak
Equal Slopes
Candy count for rating 25 (peak) is 4. This is the length of the longest slope that it’s a peak of. In this example, both slopes on it’s left and right sides are coincidentally of length 4.
This makes sense, since a longer slope means more bumps of 1’s to ensure a child gets more candy than the neighbor. Eventually, the child at peak of the slope will get the maximum number of candies.
Let’s walk up the downward slope in [0, 4, 9, 25, 8, 6, 5] and do some candy assignments:
- Rating 5: 1 candy; it’s the minimum amount.
- Rating 6: 2 candies > rating 5.
- Rating 8: 3 candies > rating 6.
- Rating 25: 4 candies > rating 8.
However, the problem is about the total number of candies and doesn’t require us to find the candy/child assignment as in the steps above.
Keeping that in mind, let’s walk down the same downward slope in [0, 4, 9, 25, 8, 6, 5] and do some candy assignments:
- Rating 25: 4 candies > rating 9.
- Rating 8: 1 candy; it’s the minimum amount.
This has no impact on the peak’s candy count since it should have at least 1+1=2 candies, and it already has 4. - Rating 6: 2 candies; downward slope (without Peak) has 2 children [8,6]. Ideally rating 6 should have 1 candy and rating 8 should have 2 candies to keep the constraint of higher rating = more candies. Since we don’t care about the exact child-candy pair, this swapping is harmless.
This has no impact on the peak’s candy count since it should have at least 2+1=3 candies, and it already has 4. - Rating 5: 3 candies; downward slope has 3 children [8, 6, 5].
Ideally rating 5 should have 1 candy, rating 6 should have 2 candies and rating 8 should have 3 candies to keep the constraint of higher rating = more candies. Since we don’t care about the exact child-candy pair, this swapping is harmless.
This has no impact on the peak’s candy count since it should have at least 3+1=4 candies, and it already has 4.
The benefit in the above approach is that the length of the downward slope simply determines the amount of candies to be given to a child.
Unequal Slopes
Let’s add a child with rating 4 at the end.
In addition to the steps in the above section, assign 4 candies to rating 4 because the downward slope has 4 children now [8, 6, 5, 4].
Does this impact the peak at rating 25? It has 4 candies. Given the slope of length 4 ahead of it, it should have 5 candies to maintain the constraint of higher rating = more candies.
So how do we fix this?
We find the Slope Diff: if the size of this downward slope is greater than or equal to the upward slope (4 ≥ 4), then add 1(slope diff) to the candy count. With a bump of 1, 4 will essentially become a 5 at the peak.
Let’s add another child with rating 3 at the end.
In addition to the steps above, assign 5 candies to rating 3 because the downward slope has 5 children now [8, 6, 5, 4, 3].
Because the size of the downward slope is greater than upward slope (5≥4), add 1 to the whole candy count. With a bump of 1, 5 will essentially become a 6 at the peak.
The code for the algorithm is as follows:
// Language: Java
// Time Complexity: O(n) Linear traversal.
// Space Complexity: O(1) Constant space for variables.public int candy(int[] ratings) {
if (ratings.length < 2) {
return ratings.length;
}
int count = 1;
int upSlopeLength = 0;
int upSlope = 0;
int downSlope = 0;
for (int i=1; i<ratings.length; i++) {
int previous = ratings[i-1];
int me = ratings[i];
// ** Equal Ratings **
if (me == previous) {
upSlope = 0;
downSlope = 0;
upSlopeLength = 0;
count += 1;
// ** Upward Slope **
} else if (me > previous) {
upSlope = upSlope == 0 ? 1 : upSlope;
upSlope += 1;
downSlope = 0;
count += upSlope;
upSlopeLength = upSlope;
// ** Downward Slope **
} else {
upSlope = 0;
downSlope += 1;
int slopeDiff =
(downSlope + 1 - upSlopeLength) > 0 ? 1 : 0;
count += downSlope + slopeDiff;
}
}
return count;
}
If you found this article useful, please help me reach more dev learners!
Show some ❤ by giving “claps” 👏 at the left margin of the page (on desktop) or at the bottom (on mobile). You can do so up to 50 times by clicking continuously!
Anum Malik
Follow NMTechBytes on Twitter for my daily tech bites :)
