[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?

Use two pass to get the minimum number of candy we give to each children. In the first pass, we scan from left to right, when ever rating[i] is greater than rating[i-1], we assign candy[i-1] + 1 to candy[i] meaning i must at least get one more candy than i-1. Otherwise we give only 1 candy. After the first sweep, we have valid the condition on left side of each child. Then on the second pass, we scan from right to left, when we find rating[i] > rating[i+1], we adjust what i get to the maximum number between candy[i] and candy[i+1]+1. After the second pass, we get what we the minimum number of candy we give to each children.

    public int candy(int[] ratings) {
        int n = ratings.length;
        if(n == 0)
            return 0; // corner case
        int[] candy = new int[n];
        candy[0] = 1; // base case
        for(int i = 1; i < n; i++) {
            candy[i] = (ratings[i] > ratings[i-1]) ? candy[i-1] + 1 : 1;
        }
        for(int i = n-2; i >= 0; i--) {
            if(ratings[i] > ratings[i+1])
                candy[i] = Math.max(candy[i], candy[i+1] + 1);
        }
        int res = 0;
        for(int i = 0; i < n; i++)
            res += candy[i];
        return res;
    }