C++ in-place solution with inline explanations

  • 0
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            // lambada cmp is used to sort people:
            //   1. by height in ascending order;
            //   2. people in same height are sort by K value in descending order
            auto cmp = [](const pair<int, int>& lhs, const pair<int, int>& rhs)
                { return (lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second > rhs.second)); };
            sort(people.begin(), people.end(), cmp);
            for(int i = 0; i < people.size(); ++i) {
                // back up the last people, it's the current tallest people with least K value
                pair<int,int> p = people.back();
                // for other un-inserted people, shift them back by one element
                for(int j = people.size()-1; j > p.second; --j) {
                    people[j] = people[j-1];
                // insert the last people to it's K value position
                people[p.second] = p;
            return people;

Log in to reply

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