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

• 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;
}
};
``````

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