# 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;
    }
};