Simple, extremely readable O(n) time O(1) space
Intuition\nSee Editorial for intuition regarding slope approach (Approach 4: Single Pass Approach with Constant Space). \nSee section below code for notes on my
# Intuition\nSee Editorial for intuition regarding slope approach (Approach 4: Single Pass Approach with Constant Space). \nSee section below code for notes on my approach.\n\n# Complexity\n- Time complexity: O(n)\n- Space complexity: O(1)\n\n# Code\n```\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        def count(n):\n            return(n*(n+1))//2\n        children = len(ratings)\n        candies, i = 0, 1\n        while i < children:\n            inc = dec = 0\n            while i < children and ratings[i] > ratings[i-1]:\n                inc += 1\n                i += 1\n            while i < children and ratings[i] < ratings[i-1]:\n                dec += 1\n                i += 1\n            if inc or dec:\n                candies += count(inc-1) + max(inc,dec) + count(dec-1)\n                continue\n            i += 1\n        return candies + children\n```\n\n# Approach\nFor a given pass of the outer while loop, we count the number of children in an increasing ratings slope then the following number of children in a decreasing ratings slope. \nFor the increasing and decreasing sequences we count the candies for each using Gauss\' formula\n`(n*(n+1))/2` with `n = length of the sequnce - 1` to leave out the peak. We handle the peak separately since it can be part of both the increasing and decreasing slope and should only be counted once based on which sequence is longer `max(inc,dec)`.\n\nOne simplification made in this solution is to not give every child a min of 1 candy but instead a min of 0 candies. We calculate the number of candies needed with this modification and then at the end bump the number of candies given to each kid up by one by adding the number of children to the candies required.\nSo for the following ratings:\n`[1, 4, 3, 2, 1]`\nwe actually calculate the following candies (solution does this as it iterates through the ratings)\n`[0, 3, 2, 1, 0]` whose sum is `6`\nand then return `6 + len(ratings) == 6 + 5 == 11`\nwhich is equivalent to\n`sum([1, 4, 3, 2, 1]) == 11`\n\n
['Python3']