LeetCode: 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?

---

We can start distribution by giving each child 1 candy. And then if child i has a higher rating than child i-1, give him one more. Then from back to the front, if child i has a higher rating than child i+1, given him the number of candies as child i+1's plus 1.

C++ Code:

/*
 * func: candy
 * goal: find the minimum candies needed to distribute
 * @param ratings: ratings of the children
 * return: minimum candies
 */
/*
 * distribute from start to end and then from end to start
 * complexity: time O(n), space O(n)
 */
int candy(vector<int> &ratings){
    if(ratings.size() == 0){
        return 0;
    }
    vector<int> candies(ratings.size(), 0);
    candies[0] = 1;
    for(int i = 1; i < ratings.size(); ++i){
        //If the child's ratings at i is higher than i-1, he should have at least one more candy
        candies[i] = ratings[i] > ratings[i-1] ? candies[i-1]+1 : 1;
    }
    //check from end to the start to ensure every child get what they need to have
    int total_candy = candies[ratings.size() - 1];
    for(int i = ratings.size() - 2; i >= 0; --i){
        candies[i] = (ratings[i] > ratings[i+1] && candies[i+1] + 1 > candies[i]) ? candies[i+1] + 1 : candies[i];
        total_candy += candies[i];
    }
    return total_candy;
}

Python Code:

# func: find the minimum candies
# @param ratings: the ratings of child
# @return: minimum candies needed
# complexity: time O(n), space O(n)
def candy(ratings):
    if not ratings:
        return 0
    candies = [1] * len(ratings)
    for i in xrange(1, len(ratings)):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1]+1

    total_candies = candies[-1]
    for i in xrange(len(ratings)-2, -1, -1):
        if ratings[i] > ratings[i+1] and candies[i] < candies[i+1] + 1:
            candies[i] = candies[i+1]+1
        total_candies += candies[i]

    return total_candies