The simplest and well-explained solution accepted as best submission in C


  • 7

    When we first encounter such problem, the least is the keyword here. There are two constraints:

    • each child will have candy which means at least one candy;
    • children with higher ratings will have more candies, which means their amount of candies is larger than neighboring children - to the left and to the right;

    Since the problem is resolved into these two constraints, then it can be easy to be handled now. The basic idea is as follows:

    • traverse from the left to the right to determine the minimal amount of candies for each child that is constrained by the left;
    • traverse from the right to the left and determine the minimal amount of candies for each child that is constrained by the right;
    • finally we can get the minimal constrained by both the left and the right neighbors for each child by retrieving the them from the results of the above two.

    Okay, by now you might be wonder how to determine the minimal constrained by the left or the right; actually it's quite intuitive that suppose we are traversing from the left to the right and set the leftmost child to 1 candy and then

    • if the next child ratings is higher ratings[i+1]>ratings[i] then limits[i+1]=limits[i]+1;
    • if the next child ratings is equal to the current one ratings[i+1]==ratings[i] then limits[i+1]=limits[i];
    • if the next child ratings is smaller (ratings[i+1] < ratings[i]) then the child is not constrained by the left now and can be any but we need to reach global minimal so limits[i]=1;

    Each child will be either constrained by the left or the right or both, but since it's constrained by the higher ratings more candies rule the minimal can only be achieved by following it; then it's the valid least amount of candies we can reach.

    Merging the two results into final limits traversing from the left to the right:

    • if the ratings[i+1] > ratings[i] then obviously limits[i+1] will be determined by the max(limits[i]+1, limits[i]) - the second parameter limits[i] here is the previous traversal (from right to left) result limits[i] constrained by the right. We have to meet the constraints of both side, so we select the higher limit here;
    • if the ratings[i+] <= ratings[i] then limits[i+1] should be less than limits[i] determined by the left but limits[i+1] which is determined by the right in the previous traversal (from right to left) is already less then limits[i]; so limits[i+1] in from-right-to-left is the valid minimal value we can get here;

    Since we have to store the limits for each child either from left to right or from right to left, so space cost will be O(n) but as an optimized option we can reuse it to reduce the space cost from 2*n to n. As for time cost, we are traversing, man! Obviously it will be O(n), to further reduce the time cost we can sum them up at the second traversal to reduce the time cost from 3 traversals to 2 traversals only.

    • Space cost O(n)
    • Time cost O(n)

    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    #define MIN(a, b) ((a) < (b) ? (a) : (b))
    //AC - 16ms;
    int candy(int* ratings, int size)
    {
        if(!size) return 0;
        int* limits = (int*)malloc(sizeof(int)*size);
        limits[size-1] = 1;
        for(int i = size-2; i >-1; i--) //from right to left;
            if(ratings[i] > ratings[i+1]) limits[i] = limits[i+1]+1;
            else limits[i] = 1;
        int sum = limits[0];
        for(int i = 1; i < size; i++) //from left to right and collect the results;
        {
            if(ratings[i] > ratings[i-1]) limits[i] = MAX(limits[i], limits[i-1]+1);
            else limits[i] = MIN(limits[i-1]-1, limits[i]);
            sum += limits[i];
        }
        return sum;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.