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?

Understand the problem:
This is a assigning candy problem. There are basically two requirements. First of all, each child must have at least one candy. Secondly, children with a higher rating get more candies than their lower rating neighbor. We can take several examples to show this problem.
For 1   2   3   3   3
      1   2   3    1   1 , so sum = 8

For 1   2   3    2   3
      1   2   3    1    2   so sum = 9

Note that we cannot sort the array, since we must maintain the neighbor relationships between each child. So we can naturally think of using DP to solve this problem.

A DP Solution:

1. Define a DP array, dp[N], where as dp[i] means number of candies for child i. 
2. Transit function:  rank[i] > rank[i - 1], dp[i] = dp[i - 1] + 1.  If rank[i] == rank[i - 1], dp[i] = 1. If rank[i] < rank[i -1], it is hard to make a decision since if dp[i - 1] = 1, we cannot let child[i] have 0 candy. So we must go back to plus 1 for all its previous visited children until meet the requirements again.

So we can see that it is actually very complicated using this way. At worst case where the array in sorted in descending order, we need to update all its previous visited children. So the time complexity is O(n^2) in the worst case. 

A better solution:

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