Java O(n^2) solution by picking the front of the queue one by one


  • 4
    F

    It looks like most of the solutions focus on the "sort & insert" idea. Here I offer another perspective to reconstruct the queue by selecting its front element from the "unordered" queue one by one. (Here "unordered" queue is the one given as the input while "ordered" queue is the one with correct order.)

    To begin, we need to determine the signature of the front element of the "ordered" queue: there should be no other element before it.

    Now in terms of the (h, k) model, what should be the h and k values of the front element? First, since there is no other element before, its k value should be 0. Second, for all those elements with k equal to 0, its h value should be the minimum. The reasoning is as follows: suppose we do have another element (h', k') with k' = 0 and h' <= h (Note we've denoted the front element as (h, k) ). Since (h, k) is the front element, it will be in front of (h', k'), which means there is at least one people, i.e. (h, k), in front of the person (h', k'). By definition of the (h, k) model, we should have k' >= 1, which contradicts with the assumption that k' = 0. Therefore we know in the (h, k) model, the front element of the "ordered" queue will be the one with k = 0 and minimum h value in the "unordered" queue.

    One more thing to consider is what happens if we have found the first front element. Straightforwardly we want to "remove" it from the "ordered" queue so that we are up to find the "next" front element. Since we've already figured out the front element of the "ordered" queue, we know that for all other people, there is at least one people (which is the front element) in front of them. For those with height greater than that of the front element, removing the front element won't matter. But for those with height no more than that of the front element, removing the front should decrease their k value by 1.

    If we have n people in the "unordered" queue, we need to pick the front element n times, and each time we need to go through the "unordered" queue to choose the front element, then modify those with height no more than the front element. This yields a time complexity of O(n^2). Here is the java program (note we need to modify the k values so I made a copy of the input "people" matrix):

    public int[][] reconstructQueue(int[][] people) {
        int n = people.length;
        int[][] copy = new int[n][];
        int[][] res = new int[n][];
            
        for (int i = 0; i < n; i++) copy[i] = Arrays.copyOf(people[i], 2);
        
        for (int i = 0; i < n; i++) {
            int k = -1;
             
            // pick the front element
            for (int j = 0; j < n; j++) {
                if (copy[j][1] == 0 && (k == -1 || copy[j][0] < copy[k][0])) k = j;
            }
                
            res[i] = people[k];   // set the result
            
            // modify the k values of those with smaller or equal h values
            for (int j = 0; j < n; j++) {
                if (copy[j][0] <= copy[k][0]) copy[j][1]--;
            }
        }
            
        return res;
    }
    

  • 0

    Nice. That's my own original solution as well. I didn't like it much anymore after seeing the sort+insert idea. But I do find it very simple.

    Here's a Python version. I put people into a pool together with a copy of their k-value, which then gets decreased during the run.

    def reconstructQueue(self, people):
        pool = [[p[1], p] for p in people]
        queue = []
        while pool:
            p = min(pool)[1]
            pool.remove([0, p])
            queue.append(p)
            for other in pool:
                if other[1][0] <= p[0]:
                    other[0] -= 1
        return queue

Log in to reply
 

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