# Share my two python solutions both O(n) time, O(n) and O(1) extra space

• The first one is O(n) space, but very concise. The idea is to find the mininum candies for each child considering only left or right neighbors.

``````class Solution:
# @param ratings, a list of integer
# @return an integer
def candy(self, ratings):
candies = [1] * len(ratings)
for i in xrange(len(ratings) - 1):
if ratings[i + 1] > ratings[i]:
candies[i + 1] = max(candies[i + 1], candies[i] + 1)

j = -i - 1
if ratings[j - 1] > ratings[j]:
candies[j - 1] = max(candies[j - 1], candies[j] + 1)

return sum(candies)
``````

The second one is O(1) space, a little bit more complicated. The idea is during one scan find all up-then-down hills in the ratings.

``````class Solution:
# @param ratings, a list of integer
# @return an integer
def candy(self, ratings):
if len(ratings) == 1:    return 1

def count_hill(up, down):
x, y = max(up, down), min(up, down) - 1
return (x * (x + 1) + y * (y + 1)) / 2

up = down = extra = 0
direction = ratings[1] - ratings[0]

for i in xrange(1, len(ratings)):
if direction > 0:  up += 1      # one more on the uphill side
if direction < 0:  down += 1    # one more on the downhill side

if i == len(ratings) - 1:   break

dr = ratings[i + 1] - ratings[i]
if dr == 0 or direction < 0 < dr:   # count extra for a hill
extra += count_hill(up, down)
up = down = 0
direction = dr

return extra + count_hill(up, down) + len(ratings)``````

• @yintaosong
I know it is an old thread but just in case anyone see and understand the second solution:
Could you please explain how the hill counting work?

My vague understanding is that to count a hill, it is essentially calculating the area under it ? (x * (x + 1) + y * (y + 1)) / 2 seems to be the area of two triangles but not very sure about it.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.