Question
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Stats
| Adjusted Difficulty | 4 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is a difficult question.
Directly doing it will result in a lot of trace-backs. The following picture gives a clear idea of what the problem is:
When traversing from low to high (upward sloping), just increase candy, that’s fine. But when sloping down, we would have no idea what value to set until we reach the min point. Fish Lei have a good solution of “trace-back algorithm” to re-adjust the values by traversing back to the top again.
However, I personally think the 2nd solution is way more splendid, that I will not cover 1st solution in detail.
Solution
The 2nd solution is very similar to “Trapping Rain Water”. This blog is the best explanation I found from Internet.
- For the first time, scan from left to right. If current rating is larger than the left one, give one more candy to current child than the left one.
- For the second time, scan from right to left. If current rating is larger than the right one, give one more candy to current child than the right one.
We consider the policy as two folds, left policy and right policy. Left policy means a child has more candies than his left one if his rating is higher than his left one. The first scan ensures that the distribution meets left policy. The second scan ensures that the distribution meets right policy. However, it will not violate left policy.
Code
2nd solution
public int candy(int[] ratings) {
int len = ratings.length;
if (len <= 1) return len;
int[] candy = new int[len];
candy[0] = candy[len-1] = 1;
for (int i = 1; i < len; i ++) {
if (ratings[i] > ratings[i-1])
candy[i] = candy[i-1] + 1;
else candy[i] = 1;
}
for (int i = len-2; i >= 0; i --) {
if (ratings[i] > ratings[i+1])
candy[i] = Math.max(candy[i], candy[i+1] + 1);
}
int sum = 0;
for (int i = 0; i < len; i ++) sum += candy[i];
return sum;
}