[Python] O(n) time solution, explained
Go from left to right and while increase, give the the next person +1 candy from previous, if not, leave number of candies as it was. In this way when we make t
Go from left to right and while increase, give the the next person +1 candy from previous, if not, leave number of candies as it was. In this way when we make this pass we make sure that condition that person with bigger value gets more candies fulfilled for pairs of adjusent persons where left person is smaller than right. Now, go from right to left and do the same: now we cover pairs of adjacent persons where right is smaller than left. After these two passes all persons are happy.\n\n#### Complexity\nOverall time and space complexity is `O(n)`. Remark: there is also `O(1)` space complexity solution using the idea of peaks and valleys.\n\n#### Code\n```python\nclass Solution:\n    def candy(self, R):\n        n, ans = len(R), [1]*len(R)\n        \n        for i in range(n-1):\n            if R[i] < R[i+1]:\n                ans[i+1] = max(1 + ans[i], ans[i+1])\n                \n        for i in range(n-2, -1, -1):\n            if R[i+1] < R[i]:\n                ans[i] = max(1 + ans[i+1], ans[i])\n        \n        return sum(ans)\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
[]