Python simple two-pass: forth and back
Intuition\nSome other solutions are too much complicated, which shouldn\'t be. Just play some cases to get this idea. Please up vote if you agree with this idea
# Intuition\nSome other solutions are too much complicated, which shouldn\'t be. Just play some cases to get this idea. Please up vote if you agree with this idea and let me see if you like it.\n\nOkay, just saw other friends already got this idea. I did work it out alone since it\'s pretty straightforward. Anyways, I hope my comments here help understanding.\n\n# Approach\nGoing foward to reward higher rating on the right. Going backward for higher rating on left. Generally, there is only one rule:\n- If you see a higher rating on the next child, it deserves one more candies if it didn\'t\n\n# Complexity\n- Time complexity:\n$$O(n)$$ since only two passes on the rating array.\n\n- Space complexity:\n$$O(n)$$ due to the $$give$$ list.\n\n# Code\n```\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        n = len(ratings)\n        give = [1] * n\n\n        for i in range(1, n):\n            if ratings[i] > ratings[i-1]:\n                give[i] = give[i-1] + 1\n\n        for i in range(n-2, -1, -1):\n            if ratings[i] > ratings[i+1] and give[i] <= give[i+1]:\n                give[i] = give[i+1] + 1\n\n        return sum(give)\n```
['Python3']