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?

Solution:

  1. public class Solution {
  2.   public int candy(int[] ratings) {
  3.     if (ratings == null || ratings.length == 0) return 0;
  5.     int n = ratings.length;
  7.     // arr[i] stores the num of candies of i-th kid
  8.     int[] arr = new int[n]; arr[0] = 1;
  10.     // scan from left to right
  11.     for (int i = 1; i < n; i++)
  12.       arr[i] = (ratings[i] > ratings[i - 1]) ? arr[i - 1] + 1 : 1;
  14.     // scan from right to left
  15.     int sum = arr[n - 1];
  17.     for (int i = n - 2; i >= 0; i--) {
  18.       if (ratings[i] > ratings[i + 1])
  19.         arr[i] = Math.max(arr[i], arr[i + 1] + 1);
  21.       sum += arr[i];
  22.     }
  24.     return sum;
  25.   }
  26. }