## # 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.

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 curr = 1;
int count = 1;
for (int i = 1; i < ratings.size(); ++i)
{
if (ratings[i] > ratings[i-1])
{
curr++;
}
else if (ratings[i] == ratings[i-1])
{
curr = 1;
}
else
{
if (curr == 1)
{
count += i - descHeadIdx - 1;
count++;
}
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;
}
};
``````