LeetCode 135 - Candy
This problem asks us to distribute candies to children standing in a line, based on their rating values. Each child must receive at least one candy, and any child with a higher rating than an adjacent neighbor must receive strictly more candies than that neighbor.
Difficulty: 🔴 Hard
Topics: Array, Greedy
Solution
LeetCode 135, Candy
Problem Understanding
This problem asks us to distribute candies to children standing in a line, based on their rating values. Each child must receive at least one candy, and any child with a higher rating than an adjacent neighbor must receive strictly more candies than that neighbor.
The input is an integer array ratings, where ratings[i] represents the rating of the ith child. The output is a single integer representing the minimum total number of candies needed to satisfy all conditions.
The challenge comes from the fact that the constraints are local, meaning each child only compares with immediate neighbors, but the candy assignments influence each other across the array. A child may need more candies because of the left neighbor, the right neighbor, or both.
The constraints are important:
1 <= n <= 2 * 10^40 <= ratings[i] <= 2 * 10^4
An array size of up to 20,000 elements means that inefficient repeated adjustments can become too slow. A brute-force simulation that repeatedly scans the array could degrade to quadratic time complexity, which is undesirable for the upper bound.
Several edge cases are important to consider:
- A single child must always receive exactly one candy.
- Strictly increasing ratings require increasing candy counts from left to right.
- Strictly decreasing ratings require increasing candy counts from right to left.
- Equal ratings do not impose any ordering requirement.
- Peaks and valleys can require satisfying both left and right constraints simultaneously.
A naive implementation often fails when one direction of constraints invalidates the other direction. For example, assigning candies correctly from left to right may still violate conditions on the right side.
Approaches
Brute Force Approach
A straightforward solution is to initialize every child with one candy, then repeatedly scan the array and adjust candy counts whenever a rule is violated.
For each child:
- If
ratings[i] > ratings[i - 1], thencandies[i]must be greater thancandies[i - 1]. - If
ratings[i] > ratings[i + 1], thencandies[i]must be greater thancandies[i + 1].
We can repeatedly update candy counts until no more changes are needed.
This approach eventually converges to a valid distribution because every violation is corrected incrementally. However, each update may create new violations elsewhere, requiring many repeated passes.
In the worst case, such as a strictly decreasing array, this process can require O(n) passes over O(n) elements, resulting in O(n^2) time complexity.
Optimal Greedy Approach
The key insight is that the constraints are directional.
- If ratings increase from left to right, candies must also increase.
- If ratings increase from right to left, candies must also increase in that direction.
Instead of repeatedly fixing violations, we can solve the problem in two linear passes:
- Left-to-right pass:
- Ensure every child with a higher rating than the left neighbor gets more candies.
- Right-to-left pass:
- Ensure every child with a higher rating than the right neighbor gets more candies.
The important detail is that the second pass must preserve the constraints already established by the first pass. We accomplish this by taking the maximum value between the existing candy count and the newly required value.
This greedy strategy works because every local relationship is handled exactly once in each direction.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeatedly fixes violations until stable |
| Optimal | O(n) | O(n) | Two directional greedy passes |
Algorithm Walkthrough
- Create a
candiesarray of sizen, initialized with1.
Every child must receive at least one candy, so this establishes the minimum valid baseline. 2. Perform a left-to-right pass.
For each index i from 1 to n - 1:
- If
ratings[i] > ratings[i - 1], assign:
candies[i] = candies[i - 1] + 1
This ensures that increasing rating sequences from left to right satisfy the rules. 3. Perform a right-to-left pass.
For each index i from n - 2 down to 0:
- If
ratings[i] > ratings[i + 1], assign:
candies[i] = max(candies[i], candies[i + 1] + 1)
The max operation is crucial because the child may already have enough candies from the first pass. We only increase the value if necessary.
4. Sum all values in the candies array.
The resulting total is the minimum valid candy distribution.
Why it works
The algorithm works because every constraint involves only adjacent children.
The left-to-right pass guarantees that every child with a higher rating than the left neighbor receives more candies. The right-to-left pass guarantees the same for the right neighbor.
Using max during the second pass preserves previously satisfied constraints while enforcing new ones. Since every local constraint is satisfied after both passes, the final distribution is valid. Because we only increase candy counts when necessary, the total is minimal.
Python Solution
from typing import List
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n
# Left-to-right pass
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# Right-to-left pass
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)
The implementation begins by initializing every child with one candy. This guarantees the minimum requirement immediately.
The first loop scans from left to right. Whenever the current rating exceeds the previous rating, the current child must receive one more candy than the previous child.
The second loop scans from right to left. This handles decreasing sequences that the first pass cannot fully address. The max operation prevents overwriting a valid larger value assigned during the first pass.
Finally, the algorithm sums the candy counts and returns the result.
Go Solution
func candy(ratings []int) int {
n := len(ratings)
candies := make([]int, n)
for i := 0; i < n; i++ {
candies[i] = 1
}
// Left-to-right pass
for i := 1; i < n; i++ {
if ratings[i] > ratings[i-1] {
candies[i] = candies[i-1] + 1
}
}
// Right-to-left pass
for i := n - 2; i >= 0; i-- {
if ratings[i] > ratings[i+1] {
if candies[i] < candies[i+1]+1 {
candies[i] = candies[i+1] + 1
}
}
}
total := 0
for _, candy := range candies {
total += candy
}
return total
}
The Go implementation follows the same logic as the Python solution.
Go does not provide a built-in max function for integers, so the comparison is implemented manually with an if statement.
Slices are used instead of arrays because the input size is dynamic. Integer overflow is not a concern because the maximum possible answer fits comfortably within Go's standard integer range.
Worked Examples
Example 1
Input:
ratings = [1,0,2]
Initial state:
| Index | Rating | Candies |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 2 | 2 | 1 |
After left-to-right pass:
ratings[1] < ratings[0], no changeratings[2] > ratings[1], setcandies[2] = candies[1] + 1 = 2
| Index | Rating | Candies |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 2 | 2 | 2 |
After right-to-left pass:
ratings[1] < ratings[2], no changeratings[0] > ratings[1], setcandies[0] = max(1, 1 + 1) = 2
| Index | Rating | Candies |
|---|---|---|
| 0 | 1 | 2 |
| 1 | 0 | 1 |
| 2 | 2 | 2 |
Final answer:
2 + 1 + 2 = 5
Example 2
Input:
ratings = [1,2,2]
Initial state:
| Index | Rating | Candies |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 2 | 1 |
| 2 | 2 | 1 |
After left-to-right pass:
ratings[1] > ratings[0], setcandies[1] = 2ratings[2] == ratings[1], no change
| Index | Rating | Candies |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 2 | 2 |
| 2 | 2 | 1 |
After right-to-left pass:
ratings[1] == ratings[2], no changeratings[0] < ratings[1], no change
Final candies:
| Index | Rating | Candies |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 2 | 2 |
| 2 | 2 | 1 |
Final answer:
1 + 2 + 1 = 4
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Two linear passes over the array |
| Space | O(n) | Extra candy array of size n |
The algorithm performs exactly two traversals of the ratings array, making the runtime linear in the number of children.
An additional array is required to store candy assignments, resulting in linear auxiliary space usage.
Test Cases
from typing import List
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)
solution = Solution()
assert solution.candy([1, 0, 2]) == 5 # Basic valley case
assert solution.candy([1, 2, 2]) == 4 # Equal ratings
assert solution.candy([1]) == 1 # Single child
assert solution.candy([1, 2, 3, 4]) == 10 # Strictly increasing
assert solution.candy([4, 3, 2, 1]) == 10 # Strictly decreasing
assert solution.candy([1, 3, 2, 2, 1]) == 7 # Peak followed by plateau
assert solution.candy([1, 2, 3, 1, 0]) == 9 # Increasing then decreasing
assert solution.candy([1, 2, 87, 87, 87, 2, 1]) == 13 # Large plateau
assert solution.candy([5, 4, 3, 2, 1, 2, 3]) == 18 # Valley in middle
assert solution.candy([1, 3, 4, 5, 2]) == 11 # Peak at end
| Test | Why |
|---|---|
[1,0,2] |
Validates valley handling |
[1,2,2] |
Ensures equal ratings do not force extra candies |
[1] |
Smallest possible input |
[1,2,3,4] |
Tests increasing sequence |
[4,3,2,1] |
Tests decreasing sequence |
[1,3,2,2,1] |
Tests plateau behavior |
[1,2,3,1,0] |
Tests mixed increasing and decreasing slopes |
[1,2,87,87,87,2,1] |
Ensures equal peaks handled correctly |
[5,4,3,2,1,2,3] |
Tests deep valley structure |
[1,3,4,5,2] |
Tests peak followed by drop |
Edge Cases
Single Child
If the input contains only one child, the answer must be 1. This case is easy to overlook because many implementations assume neighbors exist. The algorithm handles it naturally because the candy array initializes with one candy and both passes perform zero iterations.
Strictly Decreasing Ratings
An input like [5,4,3,2,1] is a common source of bugs. A left-to-right pass alone would assign every child one candy, which violates the constraints. The right-to-left pass fixes this by propagating larger candy counts backward through the decreasing sequence.
Equal Adjacent Ratings
Equal ratings do not require unequal candy counts. For example, [2,2,2] should produce [1,1,1], not increasing values. Incorrect implementations sometimes use >= instead of >, which unnecessarily increases candy assignments. This solution correctly checks only for strictly greater ratings.
Peak Structures
Arrays with local maxima, such as [1,3,4,5,2], require satisfying constraints from both directions simultaneously. A child at the peak must have more candies than both neighbors. The two-pass strategy handles this correctly because the second pass preserves previously established values using max().