# Constant-space Java solution in one pass

• Give 1st child one candy. For the subsequent children, cope with as follows:
assuming the child i - 1 have been allocated candies, then the next child (child i) will be allocated candies as one of the following ways:
(1) when ratings[i] == ratings[i-1], one candy ;
(2) when ratings[i] > ratings[i-1], 1 + the candies of previous child (child i-1) ;
(3) when ratings[i] < ratings[i-1], count length of the continuous decrease array (mark as len), and we could figure out the sum of candies for child i-1, i, i+1, i -1 + len -1.

The pattern indicates the idea of this solution.

``````       &
&
&
& & & & &
&
&
&
``````
``````public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0)
return 0;

int totalCnt = 1;
int preCandyCnt = 1; //previous child's candy number
int i = 1;
while (i < ratings.length){
if (ratings[i] == ratings[i-1]){
totalCnt += 1;
preCandyCnt = 1;
i++;
}else if (ratings[i] > ratings[i-1]){
totalCnt += preCandyCnt+1;
preCandyCnt = preCandyCnt+1;
i++;
}else{
//desent length of Array from i-1, lenth is j - (i-1)
int j = i;
while(j < ratings.length && ratings[j] < ratings[j-1])
j++;
int lenDesc = j - (i-1);

if (preCandyCnt < lenDesc)
totalCnt += lenDesc-preCandyCnt;
totalCnt += (lenDesc-1 + 1) * (lenDesc-1) / 2;
preCandyCnt = 1;
i = j;
}
}