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:
https://gist.github.com/adamkorg/6308ae6d8c7dfeb42d45c020022b9af3
And here is the code for the O(n) 2 vector solution:
https://gist.github.com/adamkorg/3bb831b738dd1b1658149d1580357b0d
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.