# A concise C++ solution for STL lovers

• 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)

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

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