Two C++ solutions given with explanation (both with O(N) time, one with O(1) space, the other with O(N) space)


  • 25
    D

    The question requires us to make sure a child with a higher rate has more candies than its left and right neighbors. One simple solution is to do two scans: one foward scan (from 1 to N-1) to make sure child i has more candies than its left neighbor if its rate is higher than its left neighbor. After the forward scan, we can guarantee that the left neighbor relationship is correct but we have to do more to make the right neighbor relationship in order; so we do the backwarad scan (from N-2 to 0) to make child i has more candies than its right neighbor i+1 if its rate is higher than its right neighbor. In the following implementation, we need a O(N) array number to save the number of candies needed for children, so it has O(N) space complexity and we do two linear scans so the time complexity is O(N)

    class Solution {
    public:
        int candy(vector<int>& ratings) {
            int len = ratings.size(), res = 0, i;
            if(len>0)
            {
                vector<int> number(len,0); // to save the number of candies for child[0:N-1]
                number[0] = 1; 
    // forward scan to calculate how many candies needed for child i to make sure it has more candies than its left neighbor if it has a higher rate, otherwise, give one candy to it
                for(i=1; i<len;++i) number[i] = ratings[i]>ratings[i-1]?number[i-1]+1:1;
    
    // backward scan to calculate to make sure child i has more candies than its right neighbor if it has a higher rate, pick the bigger one from forward and backward scans as the final number for child i
                for(i=len-2, res = number[len-1]; i>=0;--i)
                {
                    if( (ratings[i]>ratings[i+1]) && number[i]<(number[i+1]+1) ) number[i] = number[i+1]+1;
                    res += number[i];
                }
            }
            return res;
        }
    };
    

    Now, the question is can we do better? Do we really need two scans? If we do only forward scan, then the problem is we can not guarantee the right neighbor relationship holds. i.e. we don't know if the following order is descending (i>i+1>i+2>...). and that may cause issues. To fix that, we will detect the dips (the points at which the order switchs from increasing to decreasng). We will make sure all the local dips (minimum points) has only one candy and update its previous neighbors (which has hgher rates than its rate) accordingly. To do such update, we need to know when the decrease starts, so we use pPos to save that starting points.
    So the solution becomes: do the forward scan, if it is in an increasing order (child i rate > child i-1 order), check if it is a local dip (neg_peak == true): if so, update the candy number to make sure child i-1 has one candy. if not, just give one more candy to child i. If it is in an decreasing order (child i rate < child i-1 order)
    , just give one less candy to i. don't forget at last, we still need to make sure child N-1 has one or more candy. So O(1) space , O(N) time

        class Solution {
        public:
            int candy(vector<int>& ratings) {
                const int len = ratings.size();
                if(len<=1) return len;
                
                int i, pPos, res=1, peak=1; // peak: # candies given to the i-1 child
                bool neg_peak = false; // flag to indicate if it is a local dip
                for(i=1; i<len;i++)
                {
                    if(ratings[i] >= ratings[i-1]) 
                    {   // it is increasing
                        if(neg_peak) 
                        {  // it is a local dip, we need to make sure i-1 has one candy
                            res -= (peak-1) * (i-pPos - (peak>0));
                            peak = 1;
                            neg_peak = false;
                        }
                       // update child i candy number, if equal, set to 1
                        peak = (ratings[i] == ratings[i-1])? 1:++peak;
                        res += peak;
                    }
                    else
                    { // decreasing, just give one less candy, if it is the starting point of a decrease, update pPos
                        if(!neg_peak) {pPos = i-1; neg_peak = true;}
                        res += --peak;
                    }
                }
    // don't forget to update res, if the last one is a local dip
                return !neg_peak? res : res - (peak-1) * (i-pPos - (peak>0));
        
            }
        };

  • 0
    L

    How do you know that the updates done during the right-to-left pass does not break the first guarantee?


  • 0

    @dong.wang.1694

    Second Solution is so brilliant!!!!


Log in to reply
 

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