Candy (LeetCode Greedy)

Question: 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?

Idea: Greedy. Without loss of generality, let us assume the minimum assignment to each child is 0 (we can easily add N at the end to fulfill the 1 candy restriction). Then from left to right, if the ratings are increasing monotonically, add 1 candy per index, otherwise start again from 0 candy. Now if we only look from the left to the right, the problem is solved. However, the assignment should also be valid from right to left. So we need to update the assignment from right to left to fulfill the right to left requirement. After the left-to-right assignment and the right-to-left adjustment, accumulate the number of candies and add N to the final result, since each child should have at least 1 candy.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public int candy(int[] ratings) {  
     int n=ratings.length;  
     int[] count=new int[n];  
     for(int i=1;i<n;i++)  
     {  
       if(ratings[i]>ratings[i-1])  
         count[i]=count[i-1]+1;  
     }  
     for(int i=n-2;i>=0;i--)  
     {  
       if(ratings[i]>ratings[i+1]&&count[i]<=count[i+1])  
         count[i]=count[i+1]+1;  
     }  
     int sum=0;  
     for(int i=0;i<n;i++)  
       sum+=count[i];  
     return sum+n;  
   }  
 }