Candy — LeetCode 135 Python Solution

The problem

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

Example

Input

ratings = [1,0,2]

Output

5

Explanation

You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Python solution

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        left = [1] * n
        right = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
        return sum(max(a, b) for a, b in zip(left, right))

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 135. Candy is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems