LeetCode · #135

Candy Solution

Distribute candies so every child has at least one, and any child with a higher rating than a neighbor gets more candies than that neighbor.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #135

🏗️

Pattern

Greedy — two directional passes

Each child must get at least one candy. Local comparisons with neighbors create two directional constraints: higher than left neighbor, and higher than right neighbor. The greedy trick is to satisfy both directions with two passes and take the maximum requirement at each index.

Example 1

Input: ratings = [1,0,2]
Output: 5 // candies = [2,1,2]

Example 2

Input: ratings = [1,2,2]
Output: 4 // candies = [1,2,1]

Constraints

• 1 ≤ n ≤ 2 × 10⁴ • 0 ≤ ratings[i] ≤ 2 × 10⁴

Section Two · Approach 1

Repeated Relaxation — O(n²)

Start everyone with one candy. Then repeatedly scan the array and increase candies wherever a rating rule is violated. Continue until no changes happen.

Problem: This behaves like constraint relaxation and may require many passes over the array. But the constraints are only left-to-right and right-to-left, so we can satisfy them directly with exactly two linear passes.

Java — Repeated updates until stable

 import java.util.Arrays;
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
        Arrays.fill(candies, 1);
boolean changed = true;
while (changed) {
            changed = false;
for (int i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    changed = true;
                }
if (i + 1 < n && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    changed = true;
                }
            }
        }
int sum = 0;
for (int c : candies) sum += c;
return sum;
    }
}

Python — Repeated updates until stable

 class Solution:
def candy(self, ratings: list[int]) -> int:
        candies = [1] * len(ratings)
        changed = True while changed:
            changed = False for i in range(len(ratings)):
if i > 0 and ratings[i] > ratings[i-1] and candies[i] <= candies[i-1]:
                    candies[i] = candies[i-1] + 1
changed = True if i + 1 < len(ratings) and ratings[i] > ratings[i+1] and candies[i] <= candies[i+1]:
                    candies[i] = candies[i+1] + 1
changed = True return sum(candies)

Metric	Value
Time	O(n²)
Space	O(n)

Section Three · Approach 2

Two-Pass Greedy — O(n)

First pass left-to-right: if a child has a higher rating than the left neighbor, give one more candy than the left neighbor. Second pass right-to-left: if a child has a higher rating than the right neighbor, ensure it has at least one more than the right neighbor. Use max so both directional constraints remain satisfied.

💡 Mental model: Imagine hills on a road. From left-to-right, every uphill climb must increase the candy count. From right-to-left, every uphill climb in that direction must also increase the candy count. The final candy amount at each child must satisfy both hill rules, so we keep the larger requirement.

Algorithm

Initialize every child with 1 candy.
Left pass: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1.
Right pass: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1).
Sum the array.

🎯 Why max matters: The left pass may already have assigned a larger valid value. The right pass must not overwrite it with something smaller, or the left constraint would break.

Section Four · Trace

Visual Walkthrough

Trace for ratings = [1,0,2]:

Two directional constraints, one greedy array

Section Five · Implementation

Code — Java & Python

Java — Two-pass greedy

 import java.util.Arrays;
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
        Arrays.fill(candies, 1);
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1])
                candies[i] = candies[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i + 1])
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
int sum = 0;
for (int c : candies) sum += c;
return sum;
    }
}

Python — Two-pass greedy

 class Solution:
def candy(self, ratings: list[int]) -> int:
        candies = [1] * len(ratings)
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1 for i in range(len(ratings) - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Repeated relaxation	O(n²)	O(n)	Simple but inefficient
Two-pass greedy ← optimal	O(n)	O(n)	Exactly one left pass and one right pass

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All equal	`[2,2,2]`	Everyone can keep 1 candy.
Strictly increasing	`[1,2,3,4]`	Left pass alone determines answer.
Strictly decreasing	`[4,3,2,1]`	Right pass is essential.
Single child	`[5]`	Answer is 1.

⚠ Common Mistake: In the right-to-left pass, assigning candies[i] = candies[i+1] + 1 directly can destroy a larger value already established by the left pass. Always use max.

← Back to Greedy problems

LearningTree

LC 135 · Candy — Solution & Explanation | DSA Guide