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:

What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

Solution:

class Solution {
    public int candy(int[] ratings) {
        int sum = 0;
        int n = ratings.length;
        // System.out.println(Arrays.toString(ratings));
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        boolean meetReq = false;
        while (!meetReq) {
            meetReq = true;
            for (int i = 0; i < n; i ++) {
                int currRating = ratings[i];
                int prevRating = i == 0 ? Integer.MAX_VALUE : ratings[i - 1];
                int nextRating = i == n - 1 ? Integer.MAX_VALUE : ratings[i + 1];
                if (currRating > prevRating) {
                    int prevCandies = i == 0 ? 1 : candies[i - 1];
                    if (candies[i] <= prevCandies) {
                        candies[i] = prevCandies + 1;
                        meetReq = false;
                    }
                }    
                if (currRating > nextRating) {
                    int nextCandies = i == n - 1 ? 1 : candies[i + 1];
                    if (candies[i] <= nextCandies) {
                        candies[i] = nextCandies + 1;
                        meetReq = false;                        
                    }               
                }
            }
            // System.out.println(Arrays.toString(candies));
        }
        int res = 0;
        for (int c : candies) res += c;
        return res;
    }
}

class Solution {
    public int candy(int[] ratings) {
        int sum = 0;
        int n = ratings.length;
        // System.out.println(Arrays.toString(ratings));
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        for (int i = 0; i < n; i ++) {
            int currRating = ratings[i];
            int prevRating = i == 0 ? Integer.MAX_VALUE : ratings[i - 1];
            if (currRating > prevRating) {
                int prevCandies = i == 0 ? 1 : candies[i - 1];
                if (candies[i] <= prevCandies) {
                    candies[i] = prevCandies + 1;
                }
            }    

        }
        for (int i = n - 1; i >= 0; i --) {
            int currRating = ratings[i];
            int nextRating = i == n - 1 ? Integer.MAX_VALUE : ratings[i + 1];
            if (currRating > nextRating) {
                int nextCandies = i == n - 1 ? 1 : candies[i + 1];
                if (candies[i] <= nextCandies) {
                    candies[i] = Math.max(candies[i], nextCandies + 1);
                }               
            }            
        }
            // System.out.println(Arrays.toString(candies));
        int res = 0;
        for (int c : candies) res += c;
        return res;
    }
}