135. Candy¶
Edited by Charles
Hard · Python · Greedy
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
In order to follow the rules that the child with strictly higher rating must have more candies than either left or right child, we iterate the rating list from left to right once and from right to left once. For the first iteration (left → right), focus on the right child of the current child. If the right rating is strictly higher, give the number of candies that the left child holds plus one to the right child.
Original study notes follow, including intermediate snippets and earlier attempts.
Note:
- In order to follow the rules that the child with strictly higher rating must have more candies than either left or right child, we iterate the rating list from left to right once and from right to left once.
- For the first iteration (left → right), focus on the right child of the current child. If the right rating is strictly higher, give the number of candies that the left child holds plus one to the right child.
- For the second iteration (right → left), focus on the left child of the current child. This time, we cannot simply use the same way in 2 to update the candy number. Take candies = […. 4, 1] and ratings = […. 3, 2] as an example after the first iteration. The second last child should keep the candy number 4 instead of 2, although ratings[left] > ratings[right].
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | January 28, 2026 |
Python solution¶
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
result = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
result[i] = result [i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i + 1] < ratings[i]:
result[i] = max(result[i + 1] + 1, result[i])
return sum(result)