Problem

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

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.

Return the minimum number of candies you need to have to distribute the candies to the children.

Examples

Example 1:

Input:
ratings = [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:
ratings = [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.

Example 3

Input:
ratings = [2, 3, 4, 4, 3, 2, 1]
Output: 16
Explanation:
- After step 1, 2, 3 quantities distributed are– 1, 2, 3, 0, 0, 0, 0 (at this time 3rd student is marked as the last location upto which candy counter increment is needed because if we have to increase the number of candies of 3rd we need not worry about 2nd student because condition of higher candy does not breaks.)
- After 4th step – 1, 2, 3, 1, 0, 0, 0 (because 3rd and 4th student have the same grade and we have to minimize the toffee, now 4th student is marked)
- 5th Step – 1, 2, 3, 2, 1, 0, 0 (increase count till marked because we have to give at least one candy to every student and also maintain another condition of students with different grades, still 4th is marked)
- 6th step – 1, 2, 3, 3, 2, 1, 0 (still 4th is marked)
- 7th step – 1, 2, 3, 4, 3, 2, 1

Solution

Method 1 - Brute Force

A simple solution is to generate all subsets of size m of arr[0..n-1]. For every subset, find the difference between maximum and minimum elements in it. Finally return minimum difference.

Lets to better.

Method 2 - Scan From Left and Right

The problem is similar to Trapping Rain Water Problem.

  1. Do it in two directions.
  2. The first loop makes sure children with a higher rating get more candy than its left neighbour;
  3. The second loop makes sure children with a higher rating get more candy than its right neighbour. Because we have already distributed candies, to right neighbour, if it is not already max between them.

Code

Java
public int candy(int[] ratings) {
	int n = ratings.length;
	int[] ans = new int[n];
	Arrays.fill(ans, 1);
	// not starting from 0th element
	for (int i = 1; i<n; i++) {
		if (ratings[i] > ratings[i - 1]) {
			ans[i] = ans[i - 1] + 1;
		}
	}
	// not starting from last element
	for (int i = n - 2; i >= 0; i--) {
		if (ratings[i] > ratings[i+1]) {
			ans[i] = Math.max(ans[i], ans[i+1] + 1);
		}
	}

	int sum = 0;
	for (int r: ans) sum += r;

	return sum;
}

Another way to write above approach:

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

	int[] candies = new int[ratings.length];
	candies[0] = 1;

	//from let to right
	for (int i = 1; i<ratings.length; i++) {
		if (ratings[i] > ratings[i - 1]) {
			candies[i] = candies[i - 1] + 1;
		} else {
			// if not ascending, assign 1
			candies[i] = 1;
		}
	}

	int result = candies[ratings.length - 1];

	//from right to left
	for (int i = ratings.length - 2; i >= 0; i--) {
		int cur = 1;
		if (ratings[i + 1]<ratings[i]) {
			cur = candies[i + 1] + 1;
		}

		result += Math.max(cur, candies[i]);
		candies[i] = cur;
	}

	return result;
}

Dry run the algo: Example: ratings ={ 2, 3, 4, 4, 3, 2, 1} candies = {} Now, we scan from left to right and see elements are ascending. candies = {1, 2, 3, 1, 1, 1, 1}

Now we scan from right to left, with descending order: candies = {1, 2, 3, 4, 3, 2, 1}