Leetcode 135. Candy

Problem

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.

Algorithm

From left to right and then right to left to update the candies of each people, and do this untill there are any update. (How to proof only two-pass is enough? or this is just a coincidental)

Code

class Solution:
    def candy(self, ratings: List[int]) -> int:
        rlen = len(ratings)
        candies =[1] * rlen
        
        update = 1
        while update:
            update = 0
            for i in range(1, rlen):
                if ratings[i] > ratings[i-1] and candies[i] <= candies[i-1]:
                    candies[i] = candies[i-1]+1
                    update = 1

            for i in range(rlen-2, -1, -1):
                if ratings[i] > ratings[i+1] and candies[i] <= candies[i+1]:
                    candies[i] = candies[i+1]+1
                    update = 1
        
        sum_c = 0
        for i in range(rlen):
            sum_c += candies[i]
        return sum_c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22