Python Easy Code! Beats 95.82% Runtime and 94.23% Memory!
Intuition\n Describe your first thoughts on how to solve this problem. \nI used the approach of once iterating from left to right and then from right to left. H
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI used the approach of once iterating from left to right and then from right to left. Here, we had to consider kids on either sides, hence this was a good technique to achieve O(n).\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo maintain our O(n) complexity target, dynamic programming seems to be a likable option. We initialize our dp array with all 1s as each child has to have atleast one candy. We then iterate and compare with the neighbours and keep adding candies so that a child with higher rating gets more candies than neighbours.\nNote: We have to check whether the high rated child already has more candies, if so then we do not add more. So we have to compare ratings as well as candies at hand before assigning. This is because we need to allot \'minimum\' number of candies.\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n![image.png](https://assets.leetcode.com/users/images/05ae6b88-ee2c-4f3c-9fd0-81abdea06599_1690264401.968263.png)\n\n# Code\n```\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        n = len(ratings)\n        dp = [1]*n\n        #left to right\n        for i in range(1,n):\n            if ratings[i]>ratings[i-1] and dp[i]<=dp[i-1]:\n                dp[i] = dp[i-1]+1\n        #right to left\n        for i in range(n-2,-1,-1):\n            if ratings[i]>ratings[i+1] and dp[i]<=dp[i+1]:\n                dp[i] = dp[i+1]+1\n        return sum(dp)\n```
['Dynamic Programming', 'Python3']