135: Candy
Hard

The O(n) space complexity solution was quite straight-forward to come up with, taking a Greedy approach to solve this problem.

Basically, it hinges on the fact that if we make 2 passes (one from start to finish and another from finish to start), if the previous element’s rating is smaller than the current element’s rating, we can distribute 1 more candy to the current element than the previous element.

• the one edge case to consider is, on the second iteration, when we are checking if the previous element’s rating is smaller than the current element’s rating, we also need to check if the current element already receives less candy when compared to the previous element (in that is the case, we would not have to do anything)
  • an example:
    • ratings: [1, 3, 6, 2]
    • candy distributed: [1, 2, 3, 1]
  • in this case, after our first pass from start to finish, the children at index 2 and 3 already satisfy the conditions so we do not have to do anything.

code

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> distributions(ratings.size(), 1);

        int ans = 0;
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i] > ratings[i-1]) {
                distributions[i] = distributions[i-1]+1;
            }
        }
        for (int i = ratings.size()-2; i >= 0; --i) {
            if (ratings[i] > ratings[i+1] && distributions[i] <= distributions[i+1]) {
                distributions[i] = distributions[i+1]+1;
            }
            ans += distributions[i+1];
        }
        ans += distributions[0];
        return ans;
    }
};

complexity

However, there does exist an O(1) solution (which only requires 1 pass).

The intuition for a solution like this is realise that for a rating distribution, like the one shown below, it also has the minimum candy distribution of:

• rating: [1, 3, 6, 9, 3, 2, 6, 7, 7, 8, 9, 1, 2]
• candy distributed: [1, 2, 3, 4, 2, 1, 2, 3, 1, 2, 3, 1, 2]

As you can see from above, there are certain peaks. Reordering the peaks in a certain order can give us an intuition on how we can solve this problem in one pass:

• rating: [1| 3, 6, 9| 3, 2| 6, 7| 7| 8, 9| 1, 2]
• candy distributed: [1| 2, 3, 4| 1, 2| 2, 3| 1| 2, 3| 1, 2]

(Maybe the example that I chose does not best represent the algorithm) Regardless, you might notice that the values in the array go through 3 states:

Code:

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> distributions(ratings.size(), 1);

        int ans = 1;
        int inc = 0, dec = 0, peak = 0;
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i] > ratings[i-1]) {
                ++inc;
                peak = inc;
                dec = 0;
                ans += inc+1;
            } else if (ratings[i] < ratings[i-1]) {
                ++dec;
                inc = 0;
                ans += dec+1 - int(peak >= dec);
            } else {
                inc = dec = peak = 0;
                ++ans;
            }
        }
        return ans;
    }
};

complexity