Each child needs a candy count that satisfies the rating comparisons with both neighbors. A pass from left to right satisfies the comparisons with the left neighbor. A second pass, from right to left, satisfies the comparisons with the right neighbor.
The constraints
I have n children standing in a queue, each with a rating. The rules are simple:
- Each child must get at least one candy
- Children with higher ratings must get more candy than their neighbors
The goal is to find the minimum number of candies needed.
A one direction baseline scans once and compares each child with the child on the left:
function candyNaive(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1);
// Only checking left neighbor
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
return candies.reduce((a, b) => a + b, 0);
}
This does not solve [1, 0, 2] because the first child still needs more candy than the middle child.
For this reason, I use two passes. The first checks each child against the left neighbor. The second checks each child against the right neighbor. The second pass uses Math.max to preserve any larger count from the first pass.
The full two pass implementation is:
function candy(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1); // Everyone starts with 1 candy
// First pass: left to right
// If current child has higher rating than left neighbor, give more candy
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Second pass: right to left
// If current child has higher rating than right neighbor,
// make sure they have at least one more candy
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
// Use Math.max to preserve what we did in first pass
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
return candies.reduce((a, b) => a + b, 0);
}
// Example usage:
const ratings = [1, 0, 2];
console.log(candy(ratings)); // Output: 5
For [1, 0, 2], the candy counts change like this:
- Initial:
[1, 1, 1] - After first pass:
[1, 1, 2](child 2 has higher rating than child 1) - After second pass:
[2, 1, 2](child 0 has higher rating than child 1, so needs at least 2)
The minimum total is 2 + 1 + 2 = 5.
The Math.max call prevents the second pass from reducing a count that already satisfies the left side constraint. If the first pass assigns 3 and the right side requirement is 2, the child keeps 3.
The same two passes in Java are:
import java.util.Arrays;
public class Candy {
public static int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
// Pass from left to right
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Pass from right to left
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 totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}
return totalCandies;
}
public static void main(String[] args) {
int[] ratings = {1, 0, 2};
System.out.println(candy(ratings)); // Output: 5
}
}
Why the passes are enough
The two passes each visit the children once, so the time complexity is O(n). The candies array uses O(n) extra space. The Math.max update is constant time. Each Math.max compares only the two neighboring counts.
Start with the minimum valid state, apply one directional constraint, then apply the other direction while preserving the stronger assignment. This pattern also applies to other problems where neighboring conditions point both ways.
Loading comments...