26 Aug 2025•Hard•Python

Candy

distribute candy to children based on ratings using two-pass greedy approach.

first pass left to right: if rating[i] > rating[i-1], give one more candy than previous. second pass right to left: if rating[i] > rating[i+1], ensure we have more than next.

take maximum of both passes to satisfy both left and right constraints. start with 1 candy for each child.

approach

initialize all with 1 candy
left pass: handle increasing sequences
right pass: handle decreasing sequences
take max to satisfy both directions

complexity

O(n) time for two passes, O(n) space for candy array. optimal greedy solution.

Solution files

Python•candy/solution.py

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

    for i in range(1, n):
      if ratings[i] > ratings[i - 1]:
        candies[i] = candies[i - 1] + 1

    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)