Candy

Greedy

Hard

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:

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:

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.

Solution & Analysis

直观的想法是每个位置先分配1，然后从左扫，如果ratings比左边大，就把糖果数+1存在leftScan[]里，再从右扫描，如果ratings比右边大，则糖果数+1，存在rightScan[]里。最后扫一遍，比较leftScan[i], rightScan[i]，取较大值计入糖果总和。

优化：第二次从右往左扫描时可以直接比较大小，

candies[i] = Math.max(candies[i], candies[i + 1] + 1);

Approach #1: Straightforward Approach - 2 Arrays - 3 Passes

From Left to Right, From Right to Left, + final loop

3 ms, faster than 75.90%

Time complexity : O(n). leftScan[] and rightScan[] arrays are traversed thrice (3 times).

Space complexity : O(n). Two arrays leftScan[] and rightScan[] of size n are used.

class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }
        int sum = 0;
        int n = ratings.length;
        int[] leftScan = new int[n];
        int[] rightScan = new int[n];
        Arrays.fill(leftScan, 1);
        Arrays.fill(rightScan, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                leftScan[i] = leftScan[i - 1] + 1; 
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                rightScan[i] = rightScan[i + 1] + 1; 
            }
        }
        for (int i = 0; i < n; i++) {
            sum +=  Math.max(leftScan[i], rightScan[i]);
        }
        return sum;
    }
}

Approach #2： One Array, Two Passes

(Optimization) Same idea, but uses only one array, and in the second pass, get the result.

• Time complexity : O(n). The array candies[] of size n is traversed twice.

• Space complexity : O(n). An array candies[] of size n is used.

public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];

        // Give each child 1 candy 
        Arrays.fill(candies, 1);

        // Scan from left to right, to make sure right higher rated child gets 1 more candy than left lower rated child
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

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

        // Scan from right to left, to make sure left higher rated child gets 1 more candy than right lower rated child
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
            sum += candies[i];
        }
        return sum;
    }
}

Approach #3: Single Pass Approach with Constant Space

From LeetCode:

This approach relies on the observation(as demonstrated in the figure below as well) that in order to distribute the candies as per the given criteria using the minimum number of candies, the candies are always distributed in terms of increments of 1. Further, while distributing the candies, the local minimum number of candies given to a student is 1. Thus, the sub-distributions always take the form:\text{1, 2, 3, ..., n}1, 2, 3, ..., nor\text{n,..., 2, 1}n,..., 2, 1, whose sum is simply given byn(n+1)/2n(n+1)/2.

Now, we can view the givenrankingsrankingsas some rising and falling slopes. Whenever the slope is rising, the distribution takes the form:\text{1, 2, 3, ..., m}1, 2, 3, ..., m. Similarly, a falling slope takes the form:\text{k,..., 2, 1}k,..., 2, 1. An issue that arises now is that the local peak point can be included in only one of the slopes. Whether to include the local peak point(\text{n}n) in the rising slope or the falling slope?

In order to decide it, we can observe that in order to satisfy both the right neighbour and the left neighbour criteria, the peak point's count needs to be the max. of the counts determined by the rising and the falling slopes. Thus, in order to determine the number of candies required, the peak point needs to be included in the slope which contains more number of points. The local valley point can also be included in only one of the slopes, but this issue can be resolved easily, since the local valley point will always be assigned a candy count of 1(which can be subtracted from the next slope's count calculations).

Coming to the implementation, we maintain two variablesold\_slopeold_slopeandnew\_slopenew_slopeto determine the occurence of a peak or a valley. We also useupupanddowndownvariables to keep a track of the count of elements on the rising slope and on the falling slope respectively(without including the peak element). We always update the total count ofcandiescandiesat the end of a falling slope following a rising slope (or a mountain). The leveling of the points inrankingsrankingsalso works as the end of a mountain. At the end of the mountain, we determine whether to include the peak point in the rising slope or in the falling slope by comparing theupupanddowndownvariables up to that point. Thus, the count assigned to the peak element becomes:\text{max}(up, down) + 1max(up,down)+1. At this point, we can reset theupupanddowndownvariables indicating the start of a new mountain.

public class Solution {
    public int count(int n) {
        return (n * (n + 1)) / 2;
    }
    public int candy(int[] ratings) {
        if (ratings.length <= 1) {
            return ratings.length;
        }
        int candies = 0;
        int up = 0;
        int down = 0;
        int old_slope = 0;
        for (int i = 1; i < ratings.length; i++) {
            int new_slope = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
            if ((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)) {
                candies += count(up) + count(down) + Math.max(up, down);
                up = 0;
                down = 0;
            }
            if (new_slope > 0)
                up++;
            if (new_slope < 0)
                down++;
            if (new_slope == 0)
                candies++;

            old_slope = new_slope;
        }
        candies += count(up) + count(down) + Math.max(up, down) + 1;
        return candies;
    }
}

One Pass

Source: https://leetcode.com/problems/candy/discuss/42770/One-pass-constant-space-Java-solution

This solution picks each element from the input array only once. First, we give a candy to the first child. Then for each child we have three cases:

1. His/her rating is equal to the previous one ->

   give 1 candy.

2. His/her rating is greater than the previous one ->

   give him (previous + 1) candies.

3. His/her rating is less than the previous one ->

   don't know what to do yet, let's just count the number of such consequent cases.

When we enter 1 or 2 condition we can check our count from 3. If it's not zero then we know that we were descending before and we have everything to update our total candies amount: number of children in descending sequence of raitings - coundDown, number of candies given at peak - prev (we don't update prev when descending). Total number of candies for "descending" children can be found through arithmetic progression formula (1+2+...+countDown). Plus we need to update our peak child if his number of candies is less then or equal to countDown.

public class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int total = 1, prev = 1, countDown = 0;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] >= ratings[i-1]) {
                if (countDown > 0) {
                    total += countDown*(countDown+1)/2; // arithmetic progression
                    if (countDown >= prev) total += countDown - prev + 1;
                    countDown = 0;
                    prev = 1;
                }
                prev = ratings[i] == ratings[i-1] ? 1 : prev+1;
                total += prev;
            } else countDown++;
        }
        if (countDown > 0) { // if we were descending at the end
            total += countDown*(countDown+1)/2;
            if (countDown >= prev) total += countDown - prev + 1;
        }
        return total;
    }
}

Reference

http://www.allenlipeng47.com/blog/index.php/2016/07/21/candy/