[LeetCode] 135. Candy

Posted on | In

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?

Example 1:

1
2
3
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

1
2
3
4
Input: [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.

Explanation 1

  1. We can use two iterations to solve this problem. Init first child have 1 candy. First iteration is from left to right, if the right child has a higher rating, then its number of candy is the left child’s number of candy plus one; else, the right child also has one candy. This iteration is guaranteed that in a one way, the higher rating children has more candy.
  2. The second iteration is from right to left, if the left child has higher rating and the left child’s number of candy is less or equal to the right child, then the number of candy for the left child is equal to the number of candy for the right child plus one.
  3. Finally, iterate all the children’s candies and return.

Solution 1

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
class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int[] arr = new int[ratings.length];
        arr[0] = 1;

        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i-1]) {
                arr[i] = arr[i-1]+1;
            } else {
                arr[i] = 1;
            }
        }

        for (int i = ratings.length-1; i >= 1; i--) {
            if (ratings[i] < ratings[i-1] && arr[i] >= arr[i-1]) {
                arr[i-1] = arr[i] + 1;
            }
        }

        int res = 0;
        for (int i = 0; i < ratings.length; i++) {
            res += arr[i];
        }
        return res;
    }
}

Explanation 2

  1. We can use only one iteration. Give the first child one candy, consider the following three situations:
    1. The current child’s rating is equal to the previous child, then the current child have one candy.
    2. The current child’s rating is greater than the previous child, then the current child have one more candy than the previous child.
    3. The current child’s rating is less than the previous child, then we don’t know how many candy give to the current child.

  2. For the above third situation, if we give 1 candy to the current child, then if the following next child has even less rating, then that child cannot have 0 candy. If we give one less candy (compare to the previous child) to the current child, then if there is no following next child, then we gave more to the current child (we should give one). Also, if there are many next child’s ratings getting lower and lower, then the previous child’s candy may need to increase. (ratings[1, 100, 3, 2, 1] the second child should have more than 2 candies).

  3. For this example ratings[1, 100, 3, 2, 1], we give the first child one candy. Start looping from the second child, it has more rating than the first child, then we give the second child one more candy than the first child, so second child has 2 candies. For the third child, the rating is 3, which is less than the second child, so we use a variable cnt to count how many children starts less and less rating. When we get till the last less rating child, we can think backward, from the above example, cnt is 3. The last less rating child is the fifth child, which gets 1 candy, this child’s previous child which is the fourth child gets 2 candies, this child’s previous child which is the third child gets 3 candies. In other word, its 1+2+...+cnt when we encounters less and less rating children. Also, we need to check start from the first less and less rating child, this child’s previous child should add candy or not. From the example, we know the third child should have 3 candies, now the second child only has 2 candies. So the second child should have 4 candies. In other word, the first getting less and less child’s previous child should add the number of (cnt+1-pre) candy. pre is the number of candy that the previous child has. In this example, it’s pre = 2. So we add 3+1-2=2 more candy to the second child.

Solution 2

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
class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int res = 1, pre = 1, cnt = 0;

        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] >= ratings[i-1]) {
                if (cnt > 0) {
                    res += cnt*(cnt+1)/2;
                    if (cnt >= pre) res += cnt + 1 - pre;
                    cnt = 0;
                    pre = 1;
                }
                pre = (ratings[i] == ratings[i-1]) ? 1 : pre + 1;
                res = res + pre;
            }
            else cnt += 1;
        }

        if (cnt > 0) {
            res += cnt*(cnt+1)/2;
            if (cnt >= pre) res += cnt + 1- pre;
        }
        return res;
    }
}