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?

[Analysis]

To solve this problem in O(n) there are several observations to be made.

1. when we scan through the ratings, there is constraint on the number of candies of i and i-1 when we are in a ascending position (ratings[i-1] < ratings[i]) but there is no constraints if we are not in such a position.
2. starting with 1 candy for each child, we should only increase the number of candies to be distributed, but never reduce it, otherwise, we would break some constraints previously calculated

The following solution is inspired by this post, with more detailed comments.

class Solution {
public:
    int candy(vector<int> &ratings) {
        vector<int> candies(ratings.size(), 1);
        
        // scanning through the ratings from left to right while 
        // maintaining the rules for all rising positions
        for (int i=1; i<ratings.size(); ++i) {
            if (ratings[i] > ratings[i-1])
                candies[i] = candies[i-1]+1;
        }
        
        int sum = 0;
        // scanning through the ratings from right to left while 
        // maintaining the rules for all rising positions 
        // (descending positions in the first loop)
        for (int i=ratings.size()-2; i>=0; --i) {
            // we only want to increase numbers, not reduce them. 
            // !(candies[i] >= candies[i+1]+1) gurantees that we will only increase it
            // if we increase a number from right to left, we will never break the right policy
            // previously assured left policy will be maintained if we only increase a number
            if (ratings[i] > ratings[i+1] && !(candies[i] >= candies[i+1]+1))
                candies[i] = candies[i+1]+1;
            sum += candies[i+1];
        }
        sum += candies[0];
        
        return sum;
    }
};

• Algorithm