C++ another O(n^2) approach sorting k instead of h


  • 0

    I see many solutions scanning from tallest people all the way to shortest people and insert them one by one.

    Here's just another approach sorting k instead of h. It may not be the most straightforward, but I believe it's always beneficial to look at the problem from a different perspective.

    The idea is to go from smallest k to largest k. Every time, we are inserting the person in a greedy way - always trying to get k taller people on the left. If can't get k, we'll insert the person on the rightmost position (actually this won't happen, we can always get k taller people on the left, else the queue is not sortable).

    For all the existing taller people in the answer array, current insertion won't affect them since only taller people can affect shorter people, not the reverse way.

    For all the existing shorter people, they'll end up being on the left of the insertion position. I know it sounds confusing as "why all shorter people will end up on the left". Here's a brief explanation: all people already in the answer array have a k' smaller than or equal to the person's k. No larger k' exists in the answer array. Thus, if we already found k people who are taller than the person, all shorter people can't be on the right, else the shorter people will have more than k' taller people on their left.

    class Solution {
    private:
        static bool comp (const pair<int, int>& a, const pair<int, int>& b) { 
            // sort k; secondary soring of h doesn't really matter
            return a.second < b.second || (a.second == b.second && a.first > b.first);
        }
        
    public:
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            vector<pair<int, int>> ans;
            sort(people.begin(), people.end(), comp);                           // put people with smaller k in the front
            
            for (auto p : people) {
                int cnt = p.second, i = 0;                                      // cnt: remaining k; i: position in answer
    
                for (; i < ans.size() && (cnt || ans[i].first < p.first); i++) {
                    // if still has remaining k, update it; else should skip all neighbored shorter people
                    if (cnt && p.first <= ans[i].first) { cnt--; }              
                }
                
                ans.insert(ans.begin() + i, p);     
            }
            
            return ans;
        }
    };
    

Log in to reply
 

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