# Two Java Solutions - O(n) space and O(1) space, Easy to read with inline comments

• My initial O(n) runtime, O(1) space solution
Cursors require much fine tuning, and prune to mistakes. Harder to debug on the spot

``````public int candy(int[] ratings) {
int max = ratings.length;   // each child gets 1 candy
int ascendingMark = 0;      // start of ascending mark; could be updated from asc or equal trend
int diff = 0;
int peakDiff = 0, descDiff = 0;

for (int i = 1; i < ratings.length; i++) {
// weird equal case requirement
if (ratings[i-1] == ratings[i]) {
diff = 0;
peakDiff = 0;
ascendingMark = i;

} else if (ratings[i-1] < ratings[i]) {
diff++;     // greater than prev increase

// ascending mark
ascendingMark = i;
max += diff;
peakDiff = diff;

} else {
diff = 0;
// descending, pad prev with a layer of +[1,1,1...]
// all the way from latest ascending mark
descDiff = (i - ascendingMark - 1);
max += (i - ascendingMark - 1);

// only updates peak if right side catches up, < than peak already
if (peakDiff <= descDiff) {
max += descDiff - peakDiff + 1;
peakDiff = descDiff + 1;
}
}
}

return max;
}
``````

O(n) Two-Pass, O(n) Space solution, referenced from Top Voted solution.
Much simpler logic and cleaner code

``````public int candy(int[] ratings) {
int[] candy = new int[ratings.length];

// left scan; fill higher --> covers last
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i-1]) {
candy[i] = candy[i-1] + 1;
}
}

// right scan; fill higher <-- covers [0]
for (int i = ratings.length-2; i >= 0; i--) {
if (ratings[i+1] < ratings[i]) {
candy[i] = Math.max(candy[i], candy[i+1] + 1);
}
}

int max = 0;
for (int k : candy) {
max += k;
}
// at least 1 candy per child
return max + ratings.length;
}
``````

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