Java O(N log N) solution


  • 0
    G

    This problem actually seems trickier than it is. First of all we sort the people so that the biggest dude stands in front of the queue. If we compare two people of the same height, we put the one in the front that has less people in front of him.

    After that, we just have to swap the elements into the right place. This operation should not require a lot of swaps in general, so the average runtime will be (due to sorting at the beginning) O(N log N).

    public int[][] reconstructQueue(int[][] people) {
            if (people == null || people.length == 0) {
                return people;
            }
            
            Arrays.sort(people, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if (b[0] == a[0]) {
                        return a[1] - b[1];
                    }
                    return b[0] - a[0];
                }    
            });
            
            for (int i = 0; i < people.length; i++) {
                if (people[i][1] != i) {
                    swapToPos(people, i);
                }
            }
            
            return people;
        }
        
        private void swapToPos(int[][] people, int i) {
            while (i > 0 && i != people[i][1]) {
                int[] tmp = people[i];
                people[i] = people[i - 1];
                people[i - 1] = tmp;
                i--;
            }
        }
    

  • 0
    L

    I believe this is not O(N log(N)) because swapToPos is worst case O(N) and the number of times it can be run seems to be worst case O(N).


  • 0
    G

    @lololololbum That was my thought at the beginning, but if it was the case, it would mean that the line cannot be correctly reordered since it would be invalid. But in theory, you are right, if we were given an invalid line, this could result in a worst case O(N^2) scenario.


Log in to reply
 

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