Hex.*

Leetcode-Candy

Posted on In
A hard question similar to 'Min Rewards'. 'peaks and valley' technique is not working properly in this coding challenge, because it contains the same values next to each other. Traverse left-to-right and right-to-right is a better option.

Questions

There are N children standing in a line. Each child is assigned a rating value.
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.
What is the minimum candies you must give?

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

Input: [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.

Key Point

  • This question can have the same number in succession. The peaks and valleys method is not very practical for this question. Because there are many situations to consider, there will be many special situations.

  • The more recommended is the left-right, right-left method~

  • It is equivalent to using the Approach3 method in Min Rewards.

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
# O(n) time | O(n) Space
class Solution:
    def candy(self, ratings: List[int]) -> int:
        candies = [1 for _ in ratings]
        
        for i in range(1, len(ratings)):
            if ratings[i-1] < ratings[i]:
                candies[i] = candies[i-1]+1
        for j in reversed(range(len(ratings)-1)):
            if ratings[j] > ratings[j+1]:
                candies[j] = max(candies[j], candies[j+1]+1)
        return sum(candies)