5-line C++ O(N^2) Time with detailed explanation

  • 0

    The idea is to consider queue construction backward. Suppose we already have the queue constructed, let's think about how the k component affects other people in the queue. Note that we only count no shorter people in front of a person, so the last shortest person in the queue has no impact of counting for any other people in the queue, i.e., if this person is removed from the queue, the counting component k is still valid for all remaining people. Now the queue is one person shorter. We can repeat this process til exhausting the queue, and this order is exactly the reverse order of how we reconstruct the queue.
    Now we can sort the given pair (h, k) with h decreasing and k increasing. It will guarantee that the first pair (h,k) must have k=0 since no other person could be no shorter and has fewer counting by our sorting standard. Now we put it in an empty array to hold the reconstructed queue. For the second pair (h,k) from sorted result, it guarantees that k=0 or 1 since only the first person we have processed could be in front this person in the queue and therefore, we just need to put the second person in position k. Then we repeat this process til all people processed.

        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& p) {
            sort(p.begin(), p.end(), [](const pair<int, int>& a, const pair<int, int>& b){
                return (a.first > b.first) || (a.first == b.first && a.second < b.second);});
            vector<pair<int, int>> res;
            for (auto& x:p) res.insert(res.begin()+x.second, x);
            return res;

  • 0

    Actually, for the reconstruction part for (auto& x:p) res.insert(res.begin()+x.second, x), I need to insert element in random position while I also need random position access, so using vector results O(N) time complexity in average and worse cases, which results O(N^2) overall time solution. I was thinking about using list for O(1) insertion, but I lost the random position access and list::iterator is not a random access type either (cannot do list.begin()+k), so it has to use advance to move iterator k times, which results O(N) anyway.
    However, I feel this could be improved somehow.

Log in to reply

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