Problem

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

OR

Given the heights of N people waiting in a line and for each person the number of taller persons in front of him, find out their position in the line

OR

You are given the following :

  • A positive number N.
  • Heights : A list of heights of N persons standing in a queue.
  • Infronts : A list of numbers corresponding to each person (P) that gives the number of persons who are taller than P and standing in front of P.

You need to return list of actual order of persons’ height.

Consider that heights will be unique.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: people = [[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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

1
2

Input: people = [[6,0],[1,4],[2,1],[4,1],[3,0],[5,0]]
Output: [[3,0],[2,1],[5,0],[4,1],[1,4],[6,0]]

Here is a visual queue for example 2:

heights = {6, 1, 2, 4, 3, 5} and in_front = {0, 4, 1, 1, 0, 0}:

Solution

Method 1 - Brute Force

One very inefficient brute force method is to try every possible permutation, which takes O(N!) time.

Method 2 - Sorting Heights in Descending Order

  1. Sort the people by height in descending order; for equal heights, sort by k in ascending order, since a smaller k means fewer people ahead in the queue.
  2. Use a linked list to insert each person at the position indicated by their k value.
  3. Continue this process for all remaining people, placing each at their respective k index.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
        list<vector<int>> lst;
        for (const auto& p : people) {
            auto it = lst.begin();
            advance(it, p[1]);
            lst.insert(it, p);
        }
        return vector<vector<int>>(lst.begin(), lst.end());
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func (Solution) ReconstructQueue(people [][]int) [][]int {
    sort.Slice(people, func(i, j int) bool {
        if people[i][0] == people[j][0] {
            return people[i][1] < people[j][1]
        }
        return people[i][0] > people[j][0]
    })
    res := make([][]int, 0, len(people))
    for _, p := range people {
        idx := p[1]
        if idx >= len(res) {
            res = append(res, p)
        } else {
            res = append(res, nil)
            copy(res[idx+1:], res[idx:])
            res[idx] = p
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	public int[][] reconstructQueue(int[][] people) {
		Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
		List<int[]> list = new LinkedList<>();
		for (int[] p : people) {
			list.add(p[1], p);
		}
		return list.toArray(new int[list.size()][]);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun reconstructQueue(people: Array<IntArray>): Array<IntArray> {
        people.sortWith(compareBy({ -it[0] }, { it[1] }))
        val res = mutableListOf<IntArray>()
        for (p in people) {
            res.add(p[1], p)
        }
        return res.toTypedArray()
    }
}
1
2
3
4
5
6
7

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        res = []
        for p in people:
            res.insert(p[1], p)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn reconstruct_queue(mut people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        people.sort_by(|a, b| {
            if a[0] == b[0] {
                a[1].cmp(&b[1])
            } else {
                b[0].cmp(&a[0])
            }
        });
        let mut res: Vec<Vec<i32>> = Vec::new();
        for p in people {
            let idx = p[1] as usize;
            res.insert(idx, p);
        }
        res
    }
}

Dry Run

1

people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

After sorting:

1

people = [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

Now comes insertion:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

p=[7,0]
List=[7,0]

p = [7,1]
List=[7,0] -> [7,1]

p=[6,1]   (insert at position 1; Now [7,1] still has only 1 person higher than them and [6,1] also has just 1 person)
List= [7,0] -> [6,1] -> [7,1]

p=[5,0]
List = [5,0] -> [7,0] -> [6,1] -> [7,1]

p=[5,2]
List = [5,0] -> [7,0] -> [5,2] -> [6,1] -> [7,1]

p=[4,4]
List = [5,0] -> [7,0] -> [5,2] -> [6,1] -> [4,4] -> [7,1]

Now convert the list to array:

1

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

Complexity

  • ⏰ Time complexity: O(n^2). O(n log n) for sorting + O(n^2) for inserting
    • If we use linked list, it takes O(p) time to insert at position p. For n elements, it will be O(n^2)
    • If we use array list, it takes O(1) time to insert, but here it is O(n) because we have to also shift the elements around. So, O(n^2) again.
  • 🧺 Space complexity: O(n)

Method 3 - Sorting Heights in Ascending Order

Create an array with as many positions as there are people. Process each person in order of increasing height, leaving the required number of spots for taller individuals who will be placed later, and insert each person into their correct position.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]  
After sorting by height: [[4,4], [5,0], [5,2], [6,1], [7,0], [7,1]]  
Result: [ ___ ___ ___ ___ ___ ___ ]  
[4, 4]: leave 4 spots and place at the next available position  
Result: [ ___ ___ ___ ___ [4, 4] ___ ]  
[5, 0]: leave 0 spots and place  
Result: [ [5, 0] ___ ___ ___ [4, 4] ___ ]  
[5, 2]: leave 2 spots, considering previous placements, and insert  
Result: [ [5, 0] ___ [5, 2] ___ [4, 4] ___ ]  
[6, 1]: leave 1 spot and insert  
Result: [ [5, 0] ___ [5, 2] [6, 1] [4, 4] ___ ]  
[7, 0]: leave 0 spots and insert  
Result: [ [5, 0] [7, 0] [5, 2] [6, 1] [4, 4] ___ ]  
[7, 1]: leave 1 spot, considering [7, 0], and insert  
Result: [ [5, 0] [7, 0] [5, 2] [6, 1] [4, 4] [7, 1] ] => Output

To simplify handling equal heights, sort by height and, for ties, process those with higher k values first. For example, sorting by height gives: [[4,4], [5,2], [5,0], [6,1], [7,1], [7,0]].

Complexity

  • ⏰ Time complexity: O(n^2). O(n log n) for sorting. O(n) in the worst case to find the appropriate spot for a person if there are n people so O(n * n) for all of them.
  • 🧺 Space complexity: O(n)

Method 4 - Segment Trees

Let’s focus on the main inefficiency in the previous method: we use an array of 1s (available spots) and, for each person, find and occupy the k-th available spot by setting it to 0. This reduces to: Given an array of 0s and 1s, find the index of the k-th 1 and set it to 0.

Since this operation is performed for every person, doing it in O(n) time leads to an overall O(n²) complexity, which is the main bottleneck. By using a segment tree, we can handle these queries in O(log n) time, greatly improving efficiency.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class SegmentTree {
    int N;
    vector<int> node;
public:
    SegmentTree(int n) {
        N = 1;
        while (N < n) N <<= 1;
        node.assign((N << 1) - 1, 0);
        for (int i = 0; i < n; ++i) node[N - 1 + i] = 1;
        for (int i = N - 2; i >= 0; --i)
            node[i] = node[(i << 1) + 1] + node[(i << 1) + 2];
    }
    int insert(int k) {
        int i = 0;
        while (i < N - 1) {
            node[i]--;
            int left = (i << 1) + 1;
            if (node[left] > k) {
                i = left;
            } else {
                k -= node[left];
                i = left + 1;
            }
        }
        node[i]--;
        return i - N + 1;
    }
};

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0];
        });
        int n = people.size();
        SegmentTree st(n);
        vector<vector<int>> res(n);
        for (const auto& p : people) {
            res[st.insert(p[1])] = p;
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

type SegmentTree struct {
    N    int
    node []int
}

func NewSegmentTree(n int) *SegmentTree {
    N := 1
    for N < n {
        N <<= 1
    }
    node := make([]int, (N<<1)-1)
    for i := 0; i < n; i++ {
        node[N-1+i] = 1
    }
    for i := N - 2; i >= 0; i-- {
        node[i] = node[(i<<1)+1] + node[(i<<1)+2]
    }
    return &SegmentTree{N, node}
}

func (st *SegmentTree) Insert(k int) int {
    i := 0
    for i < st.N-1 {
        st.node[i]--
        left := (i << 1) + 1
        if st.node[left] > k {
            i = left
        } else {
            k -= st.node[left]
            i = left + 1
        }
    }
    st.node[i]--
    return i - st.N + 1
}

type Solution struct{}

func (Solution) ReconstructQueue(people [][]int) [][]int {
    sort.Slice(people, func(i, j int) bool {
        if people[i][0] == people[j][0] {
            return people[i][1] < people[j][1]
        }
        return people[i][0] < people[j][0]
    })
    n := len(people)
    st := NewSegmentTree(n)
    res := make([][]int, n)
    for _, p := range people {
        res[st.Insert(p[1])] = p
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    class SegmentTree {
        private int N;
        private int[] node;
        SegmentTree(int n) {
            // N = Round up n to the next highest power of 2 (i.e. N = 1 for n = 1; N = 2 for n = 2; N = 4 for n = 3, 4; N = 8 for n = 5, 6, 7, 8; and so on)
			N = 1;
            while(N < n) {
                N <<= 1;
            }
            node = new int[(N << 1) - 1];  // total no of nodes in the tree: 2*N-1
            for(int i = 0; i < n; i++) {  // leaf nodes: initialize each with 1 available spot
                node[N - 1 + i] = 1;
            }
            for(int i = N - 2; i >= 0; i--) {  // internal nodes: calculate available spots as sum of available spots in child nodes
                node[i] = node[(i<<1) + 1] + node[(i<<1) + 2];  // left child: 2*i+1, right child: 2*i+2
            }
        }
        public int insert(int k) { // return the index of k'th 1 and make it 0
            int i = 0; // root node
            while(i < N - 1) {  // internal nodes
                node[i]--;  // decrement available spots by 1 as we go down towards leaf node
                int left = (i<<1) + 1;
                if(node[left] > k) {  // decide whether to go to left child or to right child based on available spots in them
                    i = left;
                } else {
                    i = left + 1;  // left + 1 means right
                    k -= node[left];  // if going to right child, reduce k by the no of available spots in left child
                }
            }
            node[i]--;  // this is the target leaf node: make 1 to 0
            return i - N + 1;  // convert to the index that caller expects; leaf nodes begin at N-1
        }
    }
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);  // compare (h, k) by h; in case of ties, compare k in reverse order
        int n = people.length;
        SegmentTree st = new SegmentTree(n);
        int[][] res = new int[n][];
        for(int[] p: people) {
            res[st.insert(p[1])] = p;  // place p at the index of the k'th available spot returned by segment tree
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
    class SegmentTree(n: Int) {
        private val N: Int
        private val node: IntArray

        init {
            var size = 1
            while (size < n) size = size shl 1
            N = size
            node = IntArray((N shl 1) - 1)
            for (i in 0 until n) node[N - 1 + i] = 1
            for (i in N - 2 downTo 0)
                node[i] = node[(i shl 1) + 1] + node[(i shl 1) + 2]
        }

        fun insert(k: Int): Int {
            var i = 0
            var kk = k
            while (i < N - 1) {
                node[i]--
                val left = (i shl 1) + 1
                if (node[left] > kk) {
                    i = left
                } else {
                    kk -= node[left]
                    i = left + 1
                }
            }
            node[i]--
            return i - N + 1
        }
    }

    fun reconstructQueue(people: Array<IntArray>): Array<IntArray> {
        people.sortWith(compareBy({ it[0] }, { it[1] }))
        val n = people.size
        val st = SegmentTree(n)
        val res = Array(n) { IntArray(2) }
        for (p in people) {
            res[st.insert(p[1])] = p
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class SegmentTree:
    def __init__(self, n: int):
        self.N = 1
        while self.N < n:
            self.N <<= 1
        self.node = [0] * ((self.N << 1) - 1)
        for i in range(n):
            self.node[self.N - 1 + i] = 1
        for i in range(self.N - 2, -1, -1):
            self.node[i] = self.node[(i << 1) + 1] + self.node[(i << 1) + 2]

    def insert(self, k: int) -> int:
        i = 0
        while i < self.N - 1:
            self.node[i] -= 1
            left = (i << 1) + 1
            if self.node[left] > k:
                i = left
            else:
                k -= self.node[left]
                i = left + 1
        self.node[i] -= 1
        return i - self.N + 1

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (x[0], x[1]))
        n = len(people)
        st = SegmentTree(n)
        res = [None] * n
        for p in people:
            res[st.insert(p[1])] = p
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

impl Solution {
    pub fn reconstruct_queue(mut people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        struct SegmentTree {
            n: usize,
            node: Vec<i32>,
        }
        impl SegmentTree {
            fn new(n: usize) -> Self {
                let mut N = 1;
                while N < n { N <<= 1; }
                let mut node = vec![0; (N << 1) - 1];
                for i in 0..n { node[N - 1 + i] = 1; }
                for i in (0..N - 1).rev() {
                    node[i] = node[(i << 1) + 1] + node[(i << 1) + 2];
                }
                SegmentTree { n: N, node }
            }
            fn insert(&mut self, mut k: i32) -> usize {
                let mut i = 0;
                while i < self.n - 1 {
                    self.node[i] -= 1;
                    let left = (i << 1) + 1;
                    if self.node[left] > k {
                        i = left;
                    } else {
                        k -= self.node[left];
                        i = left + 1;
                    }
                }
                self.node[i] -= 1;
                i - self.n + 1
            }
        }
        people.sort_by(|a, b| a[0].cmp(&b[0]).then(a[1].cmp(&b[1])));
        let n = people.len();
        let mut st = SegmentTree::new(n);
        let mut res = vec![vec![0, 0]; n];
        for p in people {
            let idx = st.insert(p[1]);
            res[idx] = p;
        }
        res
    }
}

Complexity

  • ⏰ Time complexity: O(n log n). O(n log n) for sorting. O(n) to initialize the segment tree. O(log n) to find the appropriate spot for each person so O(n * log n) for all of them.
  • 🧺 Space complexity: O(n) for storing entries in segment tree.