Candy

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

• Time: O(n) where n is the size of ratings
• Space: O(n)

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:

• if a portion of the array is strictly increasing, it is simple
  • we just need to make the current person take 1 more candy than the previous person
• if a portion of the array is strictly decreasing, it is more complicated
  • on a high-level we can treat it as a reverse increasing segment
    • e.g. for rating 9, 3, 2, instead of distributing the candy as 3, 2, 1, we could rearrange it to 1, 2, 3
  • if the decreasing segment is longer than the previous increasing segment, that implies that the overall "peak" will be higher
    • e.g. for rating 1, 9, 6, 1, the "peak" has to 3 instead of 2 since the decreasming segment is longer and of size 3
    • we should track this peak when we are going through a strictly increasing segment
    • when our decreasing segment is longer than the previous increasing segment, we should be adding 1 more candy every time (as we have to be incrementing our peak as well)
• if a portion of the array is equal, it resets the state of the array
  • this is because neither elements need to follow the restrictions as they are neither larger nor smaller than each other
  • therefore, we can always set the consequent person to require 1 candy

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

• Time: O(n) where n is the size of ratings
• Space: O(1)