[LeetCode/Python] 135. Candy

📌 Problem

[LeetCode] 135. Candy

📌 Solution

Idea

1. Base rule: Each child must get at least 1 candy
   ⇒ Create a candies array of length n, and set all values to 1

2. Left to Right
   Traverse from left to right
   If ratings[i] > ratings[i-1], then candies[i] = candies[i-1] + 1
   Otherwise, keep candies[i] = 1

3. Right to Left
   Traverse from right to left.
   If ratings[i] > ratings[i+1], then
   candies[i] = max(candies[i], candies[i+1] + 1)

4. Result
   Sum up the candies array for the minimum total.

Code

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1]*n

        # left to right
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                candies[i] = candies[i-1] + 1
        
        # right to left
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                candies[i] = max(candies[i], candies[i+1] +1)

        return sum(candies)

Complexity

• Time: $O(n)$ (two linear scans)
• Space: $O(n)$