135: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThis problem can be solved using two passes of linear scans over the give
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThis problem can be solved using two passes of linear scans over the given ratings list. First, we can allocate 1 candy to each child. Then, we can do a forward scan and check if the current child\'s rating is greater than the previous child\'s rating. If it is, we can give one more candy to the current child than the previous child. Similarly, we can do a backward scan and check if the current child\'s rating is greater than the next child\'s rating. If it is, we can give one more candy to the current child than the next child. Finally, we can return the sum of the candies allocated to all the children.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n  def candy(self, ratings: List[int]) -> int:\n    n = len(ratings)\n    candies = [1] * n  # Allocate 1 candy to each child\n    for i in range(1, n):\n        if ratings[i] > ratings[i - 1]:\n            candies[i] = candies[i - 1] + 1  # Give one more candy to current child than previous child\n    for i in range(n - 2, -1, -1):\n        if ratings[i] > ratings[i + 1]:\n            candies[i] = max(candies[i], candies[i + 1] + 1)  # Give one more candy to current child than next child\n    return sum(candies)  # Return the total number of candies allocated\n\n```
['Array', 'Greedy', 'Python', 'Python3']