The task is to find the actual order of people in a queue based on their heights and the number of taller people in front of them.

• Iterate through the given arrays and create a list of tuples containin...read more

There are ‘N’ people in a queue, so they can stand in N! ways in a queue. We one by one check for all of the permutations whether it is an actual order of people in a queue or not.

We can o...read more

Sort people by heights. Then iterate from shortest to tallest. In each step, you need an efficient way to put the next person in the correct position. Notice that the people we’ve already place...read more

We can optimize the previous approach by using Segment Tree which is a data structure used to optimize range queries. In our problem, we need to efficiently find the kth empty slot.

To do that, we can build a segment tree, such that each of its nodes gives the number of empty slots in a particular range. Generally, we represent segment tree by an array, Here we will represent segment tree by array named as ‘tree’. In this array tree[0] will be the root of segment tree that will give the number of empty slots in the range [0, N-1], tree[1] will be left child of the root, that will give the number of empty slots in the range [0, (N-1)/2], tree[2] will be the right child of the root, that will give the number of empty slots in the range [(N-1)/2+1, N-1]. In general, for any node represented by a tree[i] and gives the number of the empty slot in the range [l, r],  its left child is represented by a tree[2*i+1], which gives the number of empty slots in a range [l, (l+r)/2] and its right child is represented by a tree[2*i+2], which gives the number of empty slots in a range [(l+r)/2+1, r].

Now, we can use this segment tree to find kth empty slot efficiently, to do this we start from the root node and in each step check whether the desired empty exists in the range represented by its left node or right node.

Algorithm

1. Sort the array ‘Height’ in increasing order and arrange the elements of array ‘Infront’ such that ‘Height[i]’ and ‘Infront[i]’, represent height and infront value of the same person after sorting.
2. Create an array tree of size 4*N. It will represent our desire segment tree.
3. Build this segtree by keeping value of all leaf node 1(containing 1 empty slot), and for any internal node ‘i’ tree[i] = tree[2*i+1] + tree[2*i+2], i.e sum of its left and right child node.
4. Create an array ‘result’ of size ‘N’ and fill it with 0.
5. Run a loop where ’i’ ranges from 0 to ‘N-1’ and in each step do the following -;
   • Recursively find the (infront[i] + 1)th empty slot using segtree and update segree accordingly.
   • This can be done by calling a recursive function findEmptySlot(tree, root,  left, right,  k) where tree represents segment tree, root is the current root of segment tree, and we need to find Kth empty slot in the range [left, right] (range represent by root). We will call this function as findEmptySlot(tree, 0,  0, N-1,  infront[i] + 1). And in each recursive step do the following steps -:
     • Decrement tree[root] by 1, as one slot in the range given by root, will be occupied.
     • If left == right, i.e we are at a leaf node, then return left as it will be our desired empty slot.
     • if tree[2*root+1] >= K, i.e its left child has more than K empty slot, then recur in left subtree i.e findEmptySlot(tree, 2*root+1, left, (left+right)/2,  K), otherwise recur in right subtree i.e call findEmptySlot(tree, 2*root+2, (left+right)/2+1, right,  K-tree[2*root+1]). Note that the Kth empty slot in range represented by root will be (K - tree[2*root+1])th empty slot in range represented by right node.
   • Assign value return by this recursive function to result[i].
6. Return ‘result’.

O(N), where  ‘N’ is the number of people.

The extra space is used by the array ‘result’, matrix ‘people’ and by array ‘tree’, all of these have size ‘N’, 2*N, 4*N respectively, i.e of the order of ‘N’. Thus overall space complexity will be O(N).

O(N * log(N)), where  ‘N’ is the number of people.

Time taken by sorting will be O(N * log(N)).  Building a segment tree will take O(N) time. It takes O(log(N)) time in the worst case to find Kth empty slot using the segment tree. As there are ‘N’ people in the queue and we need to find an empty slot for each of them, So, it will take O(N * log(N)) times in finding an empty slot for each person. Thus the overall time complexity will be O(N*log(N) + N+ N*log(N)) = O(N * log(N)).

/*

    Time Complexity : O(N*log(N))

    Space Complexity : O(N)



    Where N is the number of people.

*/



import java.util.ArrayList;

import java.util.Arrays;

import java.util.Comparator;



class cmp implements Comparator {

    public int compare(int[] a, int[] b) {

        return a[0] - b[0];

    }

};



public class Solution {



    static void buildSegTree(int[] tree, int root, int left, int right) {

        if (left == right) {

            // Leaf node will have a single empty slot initially

            tree[root] = 1;

        } else {

            int mid = (left + right) / 2;

            // Recurse on the left child

            buildSegTree(tree, 2 * root + 1, left, mid);

            // Recurse on the right child

            buildSegTree(tree, 2 * root + 2, mid + 1, right);

            // Internal node will have the sum of both of its children

            tree[root] = tree[2 * root + 1] + tree[2 * root + 2];

        }

    }



    static int findEmptySlot(int[] tree, int root, int left, int right, int k) {

        // One slot in the range represented by root will be occupied.

        tree[root]--;



        if (left == right) {

            // We have find the required empty slot.

            return left;

        }



        int mid = (left + right) / 2;



        /*

         * If number of empty slot in first half is more than k, then our desired slot

         * will be Kth empty slot of first half of current range so we recurse on first

         * half of current range.

         */

        if (tree[2 * root + 1] >= k) {

            return findEmptySlot(tree, 2 * root + 1, left, mid, k);

        }



        /*

         * Our desired slot will be (k - number of empty slot in first half)th slot of

         * second half current of range so we recurse on second half of current range.

         */

        return findEmptySlot(tree, 2 * root + 2, mid + 1, right, k - tree[2 * root + 1]);

    }



    public static ArrayList findOrder(ArrayList height, ArrayList infront) {

        // Number of people in a queue.

        // Number of people in a queue.

        int n = height.size();



        /*

         * Sort the array Height in increasing order and arrange the elements of array

         * Infront such that Height[i] and Infront[i] represents height and infront

         * value of the same person after sorting.

         * 

         * This can be done with help of matrix 'people'

         */

        int[][] people = new int[n][2];

        for (int i = 0; i < n; i++) {

            people[i][0] = height.get(i);

            people[i][1] = infront.get(i);

        }



        Arrays.sort(people, new cmp());



        for (int i = 0; i < n; i++) {

            height.set(i, people[i][0]);

            infront.set(i, people[i][1]);

        }



        // Recursively build segment tree.

        int[] tree = new int[4 * n];

        buildSegTree(tree, 0, 0, n - 1);



        // It will have actual order of people in a queue.

        ArrayList result = new ArrayList();

        for (int i = 0; i < n; i++) {

            result.add(0);

        }



        // Find empty slot for each person, andd update segment tree accordingly.

        for (int i = 0; i < n; i++) {

            int slot = findEmptySlot(tree, 0, 0, n - 1, infront.get(i) + 1);

            result.set(slot, height.get(i));

        }



        return result;

    }



}

/*
    Time Complexity : O(N*log(N))
    Space Complexity : O(N)

    Where 'N' is the number of people.
*/

#include 

void buildSegTree(vector &tree, int root, int left, int right) {
    if(left == right) {
        // Leaf node will have a single empty slot initially
        tree[root] = 1;
    }
    else {
        int mid = (left + right) / 2;
        // Recurse on the left child
        buildSegTree(tree, 2*root+1, left, mid);
        // Recurse on the right child
        buildSegTree(tree, 2*root+2, mid+1, right);
        // Internal node will have the sum of both of its children
        tree[root] = tree[2*root+1] + tree[2*root+2];
    }
}

int findEmptySlot(vector &tree, int root, int left, int right, int k) {
    // One slot in the range represented by root will be occupied. 
    tree[root]--;

    if(left == right) {
        // We have find the required empty slot.
        return left;
    }

    int mid = (left + right) / 2;

    /* 
        If number of empty slot in first half is more than k,
        then our desired slot will be Kth empty slot of first half of current range
        so we recurse on first half of current range.
    */
    if(tree[2*root+1] >= k) {
        return findEmptySlot(tree, 2*root+1, left, mid, k);
    }

    /*
        Our desired slot will be (k - number of empty slot in first half)th slot 
        of second half current of range so we recurse on second half of current range.
    */
    return findEmptySlot(tree, 2*root+2, mid+1, right, k-tree[2*root+1]);
}

vector findOrder(vector &height, vector &infront) {
    // Number of people in a queue.
    int n = height.size();

    /* 
       Sort the array 'Height' in increasing order and arrange the elements
       of array 'Infront' such that 'Height[i]' and 'Infront[i]' represents 
       height and infront value of the same person after sorting.

       This can be done with help of matrix 'people'
    */
    vector> people(n, vector(2));
    for(int i = 0; i < n; i++) {
        people[i][0] = height[i];
        people[i][1] = infront[i];
    }

    sort(people.begin(), people.end());
    
    for(int i = 0; i < n; i++) {
        height[i] = people[i][0];
        infront[i] = people[i][1];
    }

    // Recursively build segment tree. 
    vector tree(4*n);
    buildSegTree(tree, 0, 0, n-1);

    // It will have actual order of people in a queue.
    vector result(n);

    // Find empty slot for each person, andd update segment tree accordingly.
    for(int i = 0; i < n; i++) {
        int slot = findEmptySlot(tree, 0, 0, n-1, infront[i]+1);
        result[slot] = height[i];
    }
    
    return result;
}

'''
    Time Complexity : O(N*log(N))
    Space Complexity : O(N)

    Where ‘N’ is the number of people.
'''


def buildSegTree(tree, root, left, right):
    if (left == right):
        # Leaf node will have a single empty slot initially
        tree[root] = 1
    else:
        mid = (left + right) // 2
        # Recurse on the left child
        buildSegTree(tree, 2*root+1, left, mid)
        # Recurse on the right child
        buildSegTree(tree, 2*root+2, mid+1, right)
        # Internal node will have the sum of both of its children
        tree[root] = tree[2*root+1] + tree[2*root+2]


def findEmptySlot(tree, root, left, right, k):
    # One slot in the range represented by root will be occupied.
    tree[root] -= 1

    if (left == right):
        # We have find the required empty slot.
        return left

    mid = (left + right) // 2

    '''
        If number of empty slot in first half is more than k,
        then our desired slot will be Kth empty slot of first half of current range
        so we recurse on first half of current range.
    '''
    if (tree[2*root+1] >= k):
        return findEmptySlot(tree, 2*root+1, left, mid, k)

    '''
        Our desired slot will be (k - number of empty slot in first half)th slot 
        of second half current of range so we recurse on second half of current range.
    '''
    return findEmptySlot(tree, 2*root+2, mid+1, right, k-tree[2*root+1])


def findOrder(height, infront):
    # Number of people in a queue.
    n = len(height)

    '''
        Sort the array ‘Height’ in increasing order and arrange the elements
        of array ‘Infront’ such that ‘Height[i]’ and ‘Infront[i]’ represents 
        height and infront value of the same person after sorting.

        This can be done with help of matrix 'people'
    '''

    people = [[height[i], infront[i]] for i in range(n)]

    people.sort()

    for i in range(n):
        height[i] = people[i][0]
        infront[i] = people[i][1]

    # Recursively build segment tree.
    tree = [0 for i in range(4*n)]
    buildSegTree(tree, 0, 0, n-1)

    # It will have actual order of people in a queue.
    result = [0 for i in range(n)]

    # Find empty slot for each person, andd update segment tree accordingly.
    for i in range(n):
        slot = findEmptySlot(tree, 0, 0, n-1, infront[i]+1)
        result[slot] = height[i]

    return result