# Is there a solution with O(n) time and O(1) space?

• I see people use an extra array to store the candy give out to each kid, and use one or two more passes to adjust the number of candies and sum them up. I'm more concerned with any O(1) space solution.

Here's my code, and I think the comment is self-explanatory. I have problem handling the case when two neighbors have the same rating. Any sparks? Thanks!

``````public int candy(int[] ratings) {
if(ratings.length == 1) return 1;
//total number of candy
int total = 0;
//current number of candies we give. suppose first kid get 1 candy. we will adjust it after the loop.
int cur = 1;
//previous kid's rating
int prevRating = ratings[0];
//minmum candy we give out to one kid
int mincandy = 1;
for(int i = 0;i < ratings.length; i++){
//I have problem here. I do not know how to handle the case where previous kid has the same rating as current one
if(prevRating == ratings[i]){
//cur = 1;? Is there a way to adjust variable cur and mincandy to get the result we want?
total += cur;
}
//if previous kid has larger rating, we decrease the current number of candy by 1
else if(prevRating > ratings[i]){
cur--;
//set minmum candy we give to a kid if necessary
if(mincandy > cur) mincandy = cur;
total += cur;
}
//if previous kid has smaller rating, we increase the current number of candy by 1
else if(prevRating < ratings[i]){
cur++;
total += cur;
}
prevRating = ratings[i];
}
//after the loop, we can adjust the total number of candies according to the minmum candy we give out to a single kid.
//for example, [4, 3, 2, 1], mincandy will be -2 here. total is -2. after the statement below, total will be 10.
total += (1-mincandy)*ratings.length;
}``````

• Even there is no contiguous equal ratings, your solution still cannot get minimum. For example [1,3,4,5,2], the minimum candies should be {1,2,3,4,1} total is 11. Your answer is {1,2,3,4,3} total is 13.

• Guaranteed O(N) time (pass once) and O(1) storage (4 int on stack)

No math formula or multiplication needed. Only basic "addition" operation.

``````class Solution {
public:
int candy(vector<int> &ratings) {

/***  The solution is O(N) && space O(1) ***/
/***  only one pass for time && only 4 int on stack for storage ***/

int current, peak, back, sum;

if (ratings.empty()) return 0;

current=1;
sum=1;
back=1;
peak=INT_MAX;

for (int i=1;i<ratings.size();i++) {
if (ratings[i]>ratings[i-1]) {
current++;
sum += current;
}

else if (ratings[i]==ratings[i-1]) {

/**  Take care of equal case: equal ratings does not need equal candy.
thus, when ratings[i]==ratings[i-1]  simply give child i 1 candy. no need
to store i-1's candy as peak because i can go up infinitely without the
necessity to bump i-1 up **/

peak=INT_MAX; // no need to check
current=1;
sum +=current;
back=1;
}
else {
if (current!=1) {// drop to 1
peak=current;
current=1;
sum += current;
back=1;
}

else { // bump all previous (all the way to back's position) up by 1
back++;
sum += back;
if (back==peak) {   // can only be true when dropping to 1 happen when ratings[i]<
// ratings[i-1],  for equal case, we set peak to INT_MAX to
//prevent it from happening here
sum++; peak++;
}
}
}
}

return sum;
}
};``````

• I've got the solution with O(n) time complexity with O(constant) space in One pass with similar idea,

# Algorithm

Start having given one candy to each kid i.e. sum = N candies to N children, Now, adjusting the sum in single pass. Repeat until End of ratings sequence

candies
2. Check the decreasing of peak -> move to depression, add the
additional candies for only the decreasing sequence after the
peak
,
3. Then check the range of decreasing & previous increasing sequence,
only if the range of decreasing is > range of increasing and that would = (decreasing range - increasing range) [ otherwise, everything's in place, Note: you only need to adjust the peak if
depression range is greater than inclination range]
4. If it's flat [i.e adjacent ratings are same], just move on,
everything's in place. [Note: the case where adjacent rating is
same, it takes care of whether it's on top -peak or bottom, also
than initial allotted unless it's declination which is handled in
step 2] [i.e. example test case : [1, 3, 3, 2, 1] =>min no. candies
= [1, 2, 3, 2, 1] , sum = 9 ]

[PS: You need to know sum of numbers sequence 1 2, 3...n = (n * (n+1)) / 2, we need this when adjusting /adding number of candies in increasing or decreasing subsequence]

I hope my code is elegant & readable enough....

``````class Solution {
public:
int candy(vector<int> &ratings) {
int n = ratings.size();
int min_candies = n;

int range = 0;
for (size_t i = 0; i < n - 1; ) {
int start = i;
while (ratings[i] < ratings[i+1] && i < n-1) ++i;
range = i - start;
min_candies += (range * (range + 1)) / 2;
if (i == n-1) break;

start = i;
while (ratings[i] > ratings[i+1] && i < n-1) ++i;
int k = i - start - 1;
min_candies += (k * (k + 1)) / 2;
if (i - start > range) min_candies += (i - start - range);
if (ratings[i] == ratings[i+1]) ++i;
}
return min_candies;
}
};
``````

• I came up with solution which is similar to TimeArrow's one. O(n) time complexity with O(1) space complexity. I have given an example in code comment for better understanding.

Here is my code:

``````class Solution {
public:
int candy(vector<int> &ratings) {
if (ratings.size() < 1) {
return 0;
}
// e.g.
// 123654321
// i    ratings[i]  </=/>   backward    diff    previous    candy_no    total
// 0    1           >       0           0       1           1           1
// 1    2           >       0           0       2           12          1 + 2 = 3
// 2    3           >       0           0       3           123         3 + 3 = 6
// 3    6           >       0           0       4           1234        6 + 4 = 10
// 4    5           <       1           3       1           12341       10 + 1 = 11
// 5    4           <       2           2       1           123421      11 + 2 - 1 + 1 = 13
// 6    3           <       3           1       1           1234321     13 + 3 - 1 + 1 = 16
// 7    2           <       4           0       1           12354321    16 + 4 + 1 = 21
// 8    1           <       5           0       1           123654321   21 + 5 + 1 = 27
int total = 1;
int backward = 0;
int previous = 1;
int diff = 0;
for (int i = 1; i < ratings.size(); ++i) {
if (ratings[i - 1] > ratings[i]) {
++backward;
if (previous < 2) {
total += backward;
if (diff > 1) {
--total;
}
}
if (diff > 0) {
--diff;
}
else {
diff = previous - 1;
}
previous = 1;
}
else if (ratings[i - 1] < ratings[i]) {
backward = 0;
diff = 0;
total += previous;
++previous;
}
else {
backward = 0;
diff = 0;
previous = 1;
}
++total;
}
}
};``````

• Here you are, O(n) time and O(1) space, no fancy data structure is used, should be easy to understand.

``````int candy( vector<int> & ratings ) {
int n = ratings.size();

int lastCount = 1;
int lastHighestIdx = 0;
int lastHighestCount = 1;
int total = 1;

for ( int i = 1; i < n; i++ ) {
if ( ratings[i - 1] == ratings[i] ) {
lastCount = 1;
lastHighestIdx = i;
lastHighestCount = lastCount;
total += lastCount;
} else if ( ratings[i - 1] < ratings[i] ) {
lastCount++;
lastHighestIdx = i;
lastHighestCount = lastCount;
total += lastCount;
} else {
int newElems = i - lastHighestIdx;

lastCount = 1;
if ( lastHighestCount == newElems ) {
lastHighestCount++;
total++;
}

total += newElems;
}
}

}``````

• Nice solution

• the best ever

• nice solution!

• if ( lastHighestCount == newElems ) {
lastHighestCount++;
total++;
}
Clever solution!

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