[LeetCode] Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

1
2
3
4
5

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Analysis

With stack:

When I started to solve this problem, I have no idea about the solution.

My first thought is sorting the array. Because it will be very hard if we are using a unsorted array and have no idea about its structure. But there are two values for each element, how should we sort it? Sorting with $h$ with descending order would be a good idea. The reason is that if we start with a small height, we have no idea about the large elements, which need to be in front of this smaller elements to make $k$ meet the requirement.

What if $h$ is the same? I would sort it with $k$ being the ascending order because if k is larger, it must be after the element with the same $h$ but smaller $k$.

So for the example input, after sorting, we will have: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

We can start processing this sorted array.

For the first element [7, 0], looks fine. We can add it to the result.
Second element [7,1], we already have one element in our result, looks like it also meet the requirement, adding it to result is fine.
But for the third one [6,1], we cannot directly add it to the result. Because in the result we have 2 elements, but third element is [6,1], which indicating that there should be one elements in the result. So we can take the [7,1] out to somewhere else(We don’t know what we should use to save this right now), and add the [6,1] into the result.
For the fourth element [5,0], looks like we need to remove every thing from the result. However, we should be able to maintain the original order of the removed value.
For element [5,2], now we only have 1 element in the result. But this element requires two elements in front of it. We need to take some elements we removed back. Which one should we take back? As I mentioned in 4, we need to keep order of the removed value. We need to take [7,0] back, since it WAS the very first element in the result.
For element [4,4], currently in result we have [5,0], [7,0] and [5,2] looks like we need to take one more elements back. To maintain the order, we need to take [6,1] back. Just think in this way, if we take [7,1] back, where should we put this [6,1]? So obviously we should take [6,1] back.
All elements are processed. We could add the elements we took out back to our result.

So to maintain the order, we should save the elements that are removed from our result to a stack. When we process an element, the heights of elements that already processed are always larger or equal to height of current element. We need to adjust the current size of result to meet the condition.

With binary tree:

We also need to sort the array like I mentioned above.

If we have a binary tree, the value will the [h, k] pair. Here we need to have a left count to track how many elements are in current node’s left subtree, including itself. With this left count, when we insert a new node, the height of this new node is of course larger or equal to current nodes, we would be able to insert it into a correct position:

If we insert the new node to the left of a current node, we treat the new node will be before the current node, and we need to update the left count of current node.
If we insert the new node to the right of a current node, we need to update k according to the left count of current value. Because when we insert it to the right, the new node will be “after” current node. And there are already “left count of current node” before the new node. So we need to update $k$ when we recursively insert it to the right.

Code

With stack:

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (int[] p1, int[] p2) -> {
            if (p1[0] != p2[0]) {
                return p2[0] - p1[0];
            } else {
                return p1[1] - p2[1];
            }
        });
        LinkedList<int[]> ret = new LinkedList<>();
        LinkedList<int[]> stack = new LinkedList<>();
        for (int i = 0; i < people.length; i++) {
            int[] p = people[i];
            while (p[1] < ret.size()) {
                stack.push(ret.pop());
            }
            while (p[1] > ret.size()) {
                ret.push(stack.pop());
            }
            ret.push(p);
        }
        while (!stack.isEmpty()) {
            ret.push(stack.pop());
        }
        int[][] result = new int[people.length][2];
        for (int i = 0; i < people.length; i++) {
            result[i] = ret.pollLast();
        }
        return result;
    }
}

public class Solution {

public int[][] reconstructQueue(int[][] people) {

Arrays.sort(people, (int[] p1, int[] p2) -> {

if (p1[0] != p2[0]) {

return p2[0] - p1[0];

} else {

return p1[1] - p2[1];

}

});

LinkedList<int[]> ret = new LinkedList<>();

LinkedList<int[]> stack = new LinkedList<>();

for (int i = 0; i < people.length; i++) {

int[] p = people[i];

while (p[1] < ret.size()) {

stack.push(ret.pop());

}

while (p[1] > ret.size()) {

ret.push(stack.pop());

}

ret.push(p);

}

while (!stack.isEmpty()) {

ret.push(stack.pop());

}

int[][] result = new int[people.length][2];

for (int i = 0; i < people.length; i++) {

result[i] = ret.pollLast();

}

return result;

}

With binary tree:

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if (people.length == 0) {
            return people;
        }
        Arrays.sort(people, (int[] p1, int[] p2) -> {
            if (p1[0] != p2[0]) {
                return p2[0] - p1[0];
            } else {
                return p1[1] - p2[1];
            }
        });
        TreeNode root = new TreeNode(people[0]);
        for (int i = 1; i < people.length; i++) {
            insert(root, new TreeNode(people[i]), people[i][1]);
        }
        int[][] ret = new int[people.length][2];
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        int i = 0;
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            ret[i++] = current.people;
            p = current.right;
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
        }
        return ret;
    }
    
    private void insert(TreeNode root, TreeNode insertNode, int currentK) {
        if (currentK < root.leftCount) {
            root.leftCount++;
            if (root.left == null) {
                root.left = insertNode;
            } else {
                insert(root.left, insertNode, currentK);
            }
        } else {
            if (root.right == null) {
                root.right = insertNode;
            } else {
                insert(root.right, insertNode, currentK - root.leftCount);
            }
        }
    }
    
    private class TreeNode {
        int[] people;
        int leftCount;
        TreeNode left;
        TreeNode right;
        
        public TreeNode(int[] people) {
            this.people = people;
            this.leftCount = 1;
            this.left = null;
            this.right = null;
        }
    }
}

public class Solution {

public int[][] reconstructQueue(int[][] people) {

if (people.length == 0) {

return people;

}

Arrays.sort(people, (int[] p1, int[] p2) -> {

if (p1[0] != p2[0]) {

return p2[0] - p1[0];

} else {

return p1[1] - p2[1];

}

});

TreeNode root = new TreeNode(people[0]);

for (int i = 1; i < people.length; i++) {

insert(root, new TreeNode(people[i]), people[i][1]);

}

int[][] ret = new int[people.length][2];

LinkedList<TreeNode> stack = new LinkedList<>();

TreeNode p = root;

while (p != null) {

stack.push(p);

p = p.left;

}

int i = 0;

while (!stack.isEmpty()) {

TreeNode current = stack.pop();

ret[i++] = current.people;

p = current.right;

while (p != null) {

stack.push(p);

p = p.left;

}

return ret;

}

private void insert(TreeNode root, TreeNode insertNode, int currentK) {

if (currentK < root.leftCount) {

root.leftCount++;

if (root.left == null) {

root.left = insertNode;

} else {

insert(root.left, insertNode, currentK);

}

} else {

if (root.right == null) {

root.right = insertNode;

} else {

insert(root.right, insertNode, currentK - root.leftCount);

}

private class TreeNode {

int[] people;

int leftCount;

TreeNode left;

TreeNode right;

public TreeNode(int[] people) {

this.people = people;

this.leftCount = 1;

this.left = null;

this.right = null;

}

Complexity

Sorting is $O(nlogn)$.

For stack solution:

Processing each element is potentially $O(n)$, since we may need to remove all elements from result or move all element prior to current element back to result.

So total complexity should be $O(n^2)$.

For binary tree solution:

If the tree is balanced, we need $O(logn)$ to insert a node, accounting for $O(nlogn)$ in total. And in-order traverse is $O(n)$. So average complexity is $O(nlogn)$.

However, the tree can be imbalanced. The worst case is still $O(n^2)$.