Description

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.

1
2
3
4
5
Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
1
2
3
4
5
6
Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
1
2
3
4
Constraints:
- n == ratings.length
- 1 <= n <= 2 * 104
- 0 <= ratings[i] <= 2 * 104

Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candy_num = [1] * n

        for pos in range(n-1):
            if ratings[pos] < ratings[pos+1]:
                candy_num[pos+1] = candy_num[pos] + 1

        total_candies = candy_num[-1]
        for pos in range(n-2, -1, -1):
            if ratings[pos] > ratings[pos+1]:
                if candy_num[pos] <= candy_num[pos + 1]:
                    candy_num[pos] = candy_num[pos + 1] + 1
            total_candies += candy_num[pos]
        
        return total_candies

# Example usage:
ratings = [1, 0, 2]
solution = Solution()
print(f"The minimum number of candies needed is: {solution.candy(ratings)}")
class Solution:
    def candy(self, ratings: List[int]) -> int:        
        res = 1

        prev_top = 1
        desc_count = 0
        prev_candies = 1

        for i in range(1,len(ratings)):
            if ratings[i] >= ratings[i-1]:
                if desc_count != 0:
                    res += (desc_count*(desc_count+1))//2
                    res += max(0, desc_count-prev_top+1)
                    desc_count = 0
                    prev_candies = 1
                prev_candies = 1 if ratings[i] == ratings[i-1] else prev_candies+1
                prev_top = prev_candies
                res += prev_candies
            else:
                desc_count += 1   

        if desc_count != 0:
            res += (desc_count*(desc_count+1))//2
            res += max(0, desc_count-prev_top+1)   

        return res     

    def candy_bak(self, ratings: List[int]) -> int:
        result = len(ratings)

        up_length = 0
        up_num = 1
        down_length = 0

        for i in range(1, len(ratings)):
          if ratings[i] > ratings[i-1]:
            up_length += 1
            up_num = up_length
            down_length = 0
            result += up_length

          elif ratings[i] < ratings[i-1]:
            if up_length == 0:
              down_length += 1

            if down_length == up_num:
              down_length += 1

            up_length = 0
            result += down_length

          else:
            up_length = 0
            down_length = 0
            up_num = 0
        return result