Leetcode and Lintcode

Candy

Problem:

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?

Have you met this question in a real interview? Yes

Example
Given ratings = [1, 2], return 3.

given ratings = [1, 1, 1], return 3.

Given ratings = [1, 2, 2], return 4. ([1,2,1]).

Leetcode link
Lintcode link

Solution:

Initialize the candy array to 1s.
First go through from left to right;
Second go through form right to left with the following condition:

  • If the current child’s rating is greater than the previous one, the current candies should be at least 1 more than the previous one
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*************************************************************************
	> File Name: Candy.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Sun 15 Nov 22:03:51 2015
 ************************************************************************/

public class Candy{
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0)
            return 0;

        int length = ratings.length;
        int[] candies = new int[length];
        Arrays.fill(candies,1);
        
        for (int i = 1; i < length; i++){
            if (ratings[i] > ratings[i-1]) {
                candies[i] = candies[i-1] + 1;
            }
        }
        
        int sum = candies[length - 1];
        for (int i = length - 2; i >= 0; i--){
            if (ratings[i] > ratings[i+1]){ 
                // Note that candies[i] may greater than (candies[i+1] + 1), so we use the max one
                candies[i] = Math.max(candies[i], candies[i+1] + 1);
            }
            sum += candies[i];
        }
        
        return sum;
    }
}