Leetcode 135: Candy

In the O(n^2) solution we just start with all 1s and then we step through each element and if ranking[i] is bigger than it’s neighbours and candy[i] is not then add 1 to candy[i]. Repeat that until we make no more increases in a complete pass.

The O(n) solution relies on calculating from left to right to get increasing sequences, where we set candy[i] to 1 + previous one if rating[i] is bigger than previous rating. We do the same for right to left to get decreasing sequences. We then take the max of those two left and right results. There is also a O(n) time and O(1) space solution but that is more complicated.

Here is the source code for the brute force O(n^2) solution:
And here is the code for the O(n) 2 vector solution:
And here is the code for the O(n) 1 vector solution:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.