# 135. Candy
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?
Example 1:
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
# Solution
Approach 1: Two passes.
Approach 2: One Pass.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
// Two passes.
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
if (n == 0)
return 0;
vector<int> val(n, 1);
for (int i = 1; i < n; ++i)
{
if (ratings[i] > ratings[i-1])
val[i] = val[i-1] + 1;
}
int count = val[n-1];
for (int i = n-2; i >= 0; --i)
{
if (ratings[i] > ratings[i+1])
val[i] = std::max(val[i], val[i+1] + 1);
count += val[i];
}
return count;
}
};
Approach 2:
// One pass.
class Solution {
public:
int candy(vector<int>& ratings) {
int descHeadIdx = 0;
int descHeadVal = 1;
int curr = 1;
int count = 1;
for (int i = 1; i < ratings.size(); ++i)
{
if (ratings[i] > ratings[i-1])
{
curr++;
descHeadIdx = i;
descHeadVal = curr;
}
else if (ratings[i] == ratings[i-1])
{
curr = 1;
descHeadIdx = i;
descHeadVal = curr;
}
else
{
if (curr == 1)
{
count += i - descHeadIdx - 1;
if (descHeadVal <= 2)
count++;
descHeadVal--;
}
curr = 1;
}
count += curr;
}
return count;
}
};
// One pass.
class Solution {
private:
int getTotal(int n ) {
return (1 + n) * n / 2;
}
public:
int candy(vector<int>& ratings) {
if (ratings.size() <= 1)
return ratings.size();
int prevSlope = 0;
int currSlope = 0;
int asc = 0;
int desc = 0;
int count = 0;
for (int i = 1; i < ratings.size(); ++i)
{
if (ratings[i] > ratings[i-1])
currSlope = 1;
else if (ratings[i] < ratings[i-1])
currSlope = -1;
else
currSlope = 0;
if (prevSlope < 0 && currSlope >= 0 || prevSlope > 0 && currSlope == 0)
{
count += getTotal(asc) + getTotal(desc) + std::max(asc, desc);
asc = 0;
desc = 0;
}
if (currSlope > 0)
asc++;
else if (currSlope < 0)
desc++;
else
count++;
prevSlope = currSlope;
}
count += getTotal(asc) + getTotal(desc) + std::max(asc, desc) + 1;
return count;
}
};