Leetcode: Candy

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:

To obtain the number of candies per child, we pass the array in both directions. From left to right assures that if a child has higher rating than his left neighbor he will get more candies and from right to left for the opposite case. Afterwards we just have to sum the array. The running time is O(n).

public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        candies[0] = 1;
        for(int i = 1; i < ratings.length; i++)
        {
            if(ratings[i]>ratings[i-1])
                candies[i] = candies[i-1] + 1;
            else
                candies[i] = 1;
        }
        int minCandies = candies[ratings.length-1];
        for(int i = ratings.length-2; i>=0; i--)
        {
            if (ratings[i] > ratings[i+1])
                candies[i] = Math.max(candies[i], candies[i+1]+1);
            minCandies += candies[i];
        }
        return minCandies;
    }
}