# My accepted O(n) , O(1) solution

• ``````class Solution {
public:
int candy(vector<int> &ratings)
{
int i = 0; // start of the sequence
int count = 1; //total number of candy needed
int n = ratings.size();  //number of childen
int lastCandy=1; //number of Candy the last child of previous sequence hold
while ( i < n - 1)
{
int j = i+1; // j is the next node of end of this sequence
int tmp =0;
if (ratings[j] > ratings[i])
{//find the whole upside sequence, it's from i to j - 1,
while(j < n && ratings[j]>ratings[j-1]) j++;
tmp = j - i - 1; // total number in up sequence, count them from 2 to (count +1) because the first one is already included in previous sequence
count += (tmp*(tmp+3)/2); // add them up
lastCandy = tmp+lastCandy;
i = j - 1;
}
else if (ratings[j] < ratings[i])
{//find the downside sequence, it's from i to j - 1;
while(j<n && ratings[j]<ratings[j-1]) j++;
// total number in down sequence, count them from (count - 1) to 1,
tmp = j - i - 1;
count += (tmp*(tmp+1)/2);
// if the last child in previous sequence has less candy than he/she should have, add it up by the down sequence number
if (tmp >= lastCandy)
count += (tmp + 1 - lastCandy);
lastCandy = 1;
i = j - 1;
}
else
count++;
lastCandy = 1;
i = j;
}
}
return count;
}
};``````

• I'm afraid this is o(n^2).

You have iterate on n twice.

• NO. Although there are two while, the second while is to find the whole up or down sequence starting from i. At the end of the inner loop i=j. There is no overlap between two while. The total iteration won't be great than n .

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