O(n log n) solution which processes children in rank order to assign candies


  • 0
    D

    I'm actually amazed by the 2-pass O(n) solutions. O(n log n) was what I was able to come up with. The key observation is that you only depend on your neighbor's ranking, and it only affects you if you have a ranking that is greater than your neighbor's ranking. Processing the children in rank order (starting with the smallest ranked child first) leads to a greedy assignment.

    class Solution {
    public:
        int candy(vector<int>& ratings) {
            vector<pair<int, int>> ridx;
            for (int i = 0; i < ratings.size(); ++i) {
                ridx.push_back(make_pair(ratings[i], i));
            }
            std::sort(ridx.begin(), ridx.end());
            vector<bool> assigned(ratings.size(), false);
            vector<int> res(ratings.size(), 0);
            int minCandies = 0;
            for (auto it: ridx) {
                int i = it.second;
                int l = it.second - 1;
                int r = it.second + 1;
                int candies = 1;
                if (l >= 0 && assigned[l] && ratings[i] > ratings[l]) {
                    candies = std::max(candies, res[l] + 1);
                }
                if (r < ratings.size() && assigned[r] && ratings[i] > ratings[r]) {
                    candies = std::max(candies, res[r] + 1);
                }
                res[i] = candies;
                assigned[i] = true;
                minCandies += candies;
            }
            return minCandies;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.