# 1 pass solution O(n) complexity O(1) space

• basic idea is:
if it's increasing ( ratings[i]> ratings[i-1]), increase by 1
if it's decreasing, decrease by 1 each node and count the number decreasing, finally when it increasing or equal again, the candy will be c (may be negative), then compensate the delta:
if(c <=0) sum+= num*(1-c);
else sum += (num-1)*(1-c);

``````public class Solution {
public int candy(int[] ratings) {
int c = 1;
int sum  = 1;
int num = 1;
for(int i = 1; i < ratings.length; i ++){
if( ratings[i]> ratings[i-1]) {   ////increasing
if(num > 1){   ////compensate the delta
if(c <=0)
sum+= num*(1-c);
else
sum += (num-1)*(1-c);
c = 2;  ///reset for current increasing candy
}
else
c++;
sum+=c;
num = 1;
}
else if(ratings[i] == ratings[i-1]) {
if(num > 1){   ////compensate the delta
if(c <=0)
sum+= num*(1-c);
else
sum += (num-1)*(1-c);
}
c=1;
sum+=c;
num = 1;
}
else{
c--; //keep decreasing
sum+=c;
num++;
}

}
if(num > 1){
if(c <=0)
sum+= num*(1-c);
else
sum += (num-1)*(1-c);
}
return sum;
}
``````

}

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