# One-pass constant space Java solution

• Hi guys!

This solution picks each element from the input array only once. First, we give a candy to the first child. Then for each child we have three cases:

1. His/her rating is equal to the previous one -> give 1 candy.
2. His/her rating is greater than the previous one -> give him (previous + 1) candies.
3. His/her rating is less than the previous one -> don't know what to do yet, let's just count the number of such consequent cases.

When we enter 1 or 2 condition we can check our count from 3. If it's not zero then we know that we were descending before and we have everything to update our total candies amount: number of children in descending sequence of raitings - coundDown, number of candies given at peak - prev (we don't update prev when descending). Total number of candies for "descending" children can be found through arithmetic progression formula (1+2+...+countDown). Plus we need to update our peak child if his number of candies is less then or equal to countDown.

Here's a pretty concise code below.

``````public class Solution {
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0) return 0;
int total = 1, prev = 1, countDown = 0;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] >= ratings[i-1]) {
if (countDown > 0) {
total += countDown*(countDown+1)/2; // arithmetic progression
if (countDown >= prev) total += countDown - prev + 1;
countDown = 0;
prev = 1;
}
prev = ratings[i] == ratings[i-1] ? 1 : prev+1;
total += prev;
} else countDown++;
}
if (countDown > 0) { // if we were descending at the end
total += countDown*(countDown+1)/2;
if (countDown >= prev) total += countDown - prev + 1;
}
}
}
``````

Have a nice coding!

• very nice answer,thanks very much!

• nice ideas. I write a similar one using c++

``````    if (ratings.size() <= 1)
return ratings.size();

ratings.push_back(ratings.back()); // push last elements for easy computing
int pre = 1, sum = 1;
int len_decrease = 0;
for (int i = 1; i < ratings.size(); ++i)
{
if (ratings[i] < ratings[i-1]) //if decreasing : count the length of decreasing segment
{
++len_decrease;
--pre;
}
else
{
if (len_decrease > 0) // if at the end of decreasing, compute sum candidate of the segment
{
if (pre < 1)    // if length of decreasing segment is greater than the previous monotone segment
sum += (2+len_decrease)*(1+len_decrease)/2 - (len_decrease+pre);
else
sum += (1+len_decrease)*len_decrease/2;
pre = 1;
len_decrease = 0;
}

if (ratings[i] > ratings[i-1]) // if increasing
++pre;
else // if equal
pre = 1;
sum += pre;
}
}

return sum-1;``````

• This is efficient, but really difficult to understand. I wrote my blog for more explanation. Hope it helps to understand.

• haha...
same as yours.

• Great job! I did the similar thing but failed to handle the desceding sequence properly. The way you treat the descending sequence as a whole and only add them & modify the peak once it ends is really nice.

• It's really clever to come up with this one-pass idea...

• Such a concise code. I came up with the same idea and spend several hours trying to implement it. But I failed.

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