Candy @LeetCode

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?

	package leetcode;
	import java.util.Arrays;
	/**
	* Solution: two pass. 1. left -> right 2. right -> left
	* (1,2,3...) left -> right solve increasing situation
	* (3,2,1...) right -> left solve decreasing situation
	*
	* Refactor:
	* 1. Use Arrays.fill(array, value) instead of for-loop
	* 2. Add candy count to sum. Use second loop but not a new one. Don't miss the head!
	*
	* @author jeffwan
	* @date Apr 4, 2014
	*/
	public class Candy {
	public int candy(int[] ratings) {
	if (ratings == null || ratings.length == 0) {
	return -1;
	}
	int[] candy = new int[ratings.length];
	int sum = 0;
	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 - 1; i > 0 ; i--) {
	if (ratings[i -1] > ratings[i] && candy[i - 1] <= candy[i]) {
	candy[i - 1] = candy [i] + 1;
	}
	sum += candy[i];
	}
	sum += candy[0];
	return sum;
	}
	}

view raw Candy.java hosted with ❤ by GitHub