A concise C++ solution for STL lovers


  • 3
    R

    If you like C++ and STL, you may also like the following solution:

    class Solution {
    public:
        int candy(vector<int> &ratings) {
            
            // Corner case:
            if (ratings.size( ) <= 1)
            {
                return ratings.size( ); // Zero or one.
            }
            
            vector<int> candies(ratings.size(), 1);             // One candy per children at least.
            extraCandies(begin(candies), end(candies),          // Extra candies, left to right.
                         begin(ratings));
            extraCandies(candies.rbegin(), candies.rend(),      // Extra candies, right to left.
                         ratings.rbegin());
            return accumulate(begin(candies), end(candies), 0); // Total summ of candies.
        }
        
        template<typename It>
        int extraCandies(It candyIt, It candyEnd, It ratingIt)
        {
            int prevCandy = *candyIt;
            int prevRating = *ratingIt;
            while(candyIt != candyEnd)
            {
                if (*ratingIt > prevRating
                    && *candyIt <= prevCandy)
                {
                    // Bingo, extra candies for him!
                    (*candyIt) = prevCandy + 1;
                }
                
                prevRating = *ratingIt;
                prevCandy = *candyIt;
                ++candyIt;
                ++ratingIt;
            }
        }
    };
    

    Complexity:

    • CPU: O(n)
    • Memory: O(n)

  • 0
    V

    You go through the array twice, then once more to accumulate.
    I think the linear solution is always preferred (educationally)


Log in to reply
 

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