O(nlogn) - efficient indexing free slots


  • 1
    T

    As others have posted, we can sort the input by ascending heights. We start with the shortest people; their k must be the exact index in the queue. We mark these slots as "occupied", remaining slots as "free". Then, for the next shortest people, their k must be the exact index in the "free" slots. And so on.

    (We can also sort by descending heights, and do positional insertions. An insertion is only affected by insertions after it, therefore it would be better to process insertions from last to first, in which case, it transforms to the solution above.)

    Suppose we have a data structure to manage occupied & free slots (in Java)

    class Slots {
        // occupy the f-th free slot; return its overall index
        int occupy(int f)
    

    then the solution to the problem can be

    public int[][] reconstructQueue(int[][] people)
    {
        Arrays.sort(people, Comparator.comparing( p -> ((long)p[0]<<32)-p[1] ));
    
        Slots slots = new Slots(people.length);
        int[][] queue = new int[people.length][];
        for(int[] p : people)
            queue[ slots.occupy(p[1]) ] = p;
        return queue;
    }
    

    How to model Slots efficiently? Slots can be modeled as leaves of a binary tree; each node in the binary tree contains a counter of its "free" leaves. To find the f-th free leaf, we descend from the root, going left or right depending on which half contains that leaf. To occupy the leaf, decrement the counters in the path.

    (Obviously, a right child is redundant, it's value can be derived from the parent and the left sibling. If we omit all right nodes, we only need N nodes, and it becomes essentially Fenwick tree / binary indexed tree. If we take advantage of the fact that leave nodes only require 1 bit, we can further cut the memory to N bits instead of ints to represent the tree.)

    Example: initial state of tree with 4 free slots, 0-th to 3-th

                 4    
               2   2
              1 1 1 1
    

    occupy the 1-th free slot

                 3    
               1   2
              1 0 1 1    // 3 free slots now
    

    occupy the 1-th of the 3 free slots

                 2    
               1   1
              1 0 0 1    
    

    The following is an implementation which uses an array to represent a complete binary tree of 2^m leaves.

    class Slots
    {
        int[] tree;
    
        Slots(int capacity)
        {
            if(capacity>(1<<30))
                throw new IllegalArgumentException("capacity too big");
    
            int N=1;  // N = 2^m >= capacity
            while(N<capacity)
                N*=2;
    
            tree = new int[2*N-1];
            for(int i=0; N>0; i=2*i+1, N/=2)
                Arrays.fill(tree, i, 2*i+1, N);
        }
    
        // occupy the f-th free slot; return its overall index
        int occupy(int f)
        {
            assert 0<=f && f<tree[0];
            return occupy(f, 0);
        }
    
        int occupy(int f, int n)
        {
            tree[n]--;
            if(n>=tree.length/2) // leaf
                return n-tree.length/2;
    
            int L = tree[2*n+1];
            if(f<L)
                return occupy(f, 2*n+1);
            else
                return occupy(f-L, 2*n+2);
        }
    
    }

Log in to reply
 

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