26 Aug 2025•Python•Hard

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 = [class="syntax-number">1] * n

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

    for i in range(n - class="syntax-number">2, -class="syntax-number">1, -class="syntax-number">1):
      if ratings[i] > ratings[i + class="syntax-number">1]:
        candies[i] = max(candies[i], candies[i + class="syntax-number">1] + class="syntax-number">1)

    return sum(candies)