Candy | Leetcode

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

---

Solution: Create an array of all ones, indicating the number of candies we will give to each child.

Go from left to right. If the right neighbor (at index i) has a higher rating than the left neighbor (at index i - 1), then give the right neighbor one more candy than the left neighbor.

Go from right to left. If the left neighbor (at index i - 1) has a higher rating than the right neighbor (at index i), then give the left neighbor one more candy than the right neighbor. But also make sure that the left neighbor has at least as many candies as what we previously decided to give to this child so that we continue to satisfy the condition for going from left to right as well.

Sum up the number of candies for each child as the answer.

public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i - 1] < ratings[i]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        for (int i = ratings.length - 1; i >= 1; i--) {
            if (ratings[i - 1] > ratings[i]) {
                candies[i - 1] = Math.max(candies[i - 1], candies[i] + 1);
            }
        }
        
        return IntStream.of(candies).sum();
    }
}