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 exactlyki 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 arraypeople. 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.
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 5with no other people taller or the same height in front.Person 1 has height 7with no other people taller or the same height in front.Person 2 has height 5with two persons taller or the same height in front, which is person 0 and 1.Person 3 has height 6with one person taller or the same height in front, which is person 1.Person 4 has height 4with four people taller or the same height in front, which are people 0,1,2, and 3.Person 5 has height 7with 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]]
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.
Use a linked list to insert each person at the position indicated by their k value.
Continue this process for all remaining people, placing each at their respective k index.
classSolution {
publicint[][]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(newint[list.size()][]);
}
}
1
2
3
4
5
6
7
8
9
10
classSolution {
funreconstructQueue(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
classSolution:
defreconstructQueue(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 {
pubfnreconstruct_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])
}
});
letmut res: Vec<Vec<i32>>= Vec::new();
for p in people {
let idx = p[1] asusize;
res.insert(idx, p);
}
res
}
}
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]
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]].
⏰ 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.
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.
classSegmentTree {
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];
}
intinsert(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;
}
};
classSolution {
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 (constauto& p : people) {
res[st.insert(p[1])] = p;
}
return res;
}
};
classSolution {
classSegmentTree {
privateint N;
privateint[] 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 =newint[(N << 1) - 1]; // total no of nodes in the tree: 2*N-1for(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 }
}
publicintinsert(int k) { // return the index of k'th 1 and make it 0int i = 0; // root nodewhile(i < N - 1) { // internal nodes node[i]--; // decrement available spots by 1 as we go down towards leaf nodeint 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 0return i - N + 1; // convert to the index that caller expects; leaf nodes begin at N-1 }
}
publicint[][]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 orderint n = people.length;
SegmentTree st =new SegmentTree(n);
int[][] res =newint[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;
}
}
classSolution {
classSegmentTree(n: Int) {
privateval N: Int
privateval node: IntArray
init {
var size = 1while (size < n) size = size shl 1 N = size
node = IntArray((N shl 1) - 1)
for (i in0 until n) node[N - 1 + i] = 1for (i in N - 2 downTo 0)
node[i] = node[(i shl 1) + 1] + node[(i shl 1) + 2]
}
funinsert(k: Int): Int {
var i = 0var kk = k
while (i < N - 1) {
node[i]--val left = (i shl 1) + 1if (node[left] > kk) {
i = left
} else {
kk -= node[left]
i = left + 1 }
}
node[i]--return i - N + 1 }
}
funreconstructQueue(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
}
}
classSegmentTree:
def __init__(self, n: int):
self.N =1while self.N < n:
self.N <<=1 self.node = [0] * ((self.N <<1) -1)
for i in range(n):
self.node[self.N -1+ i] =1for i in range(self.N -2, -1, -1):
self.node[i] = self.node[(i <<1) +1] + self.node[(i <<1) +2]
definsert(self, k: int) -> int:
i =0while i < self.N -1:
self.node[i] -=1 left = (i <<1) +1if self.node[left] > k:
i = left
else:
k -= self.node[left]
i = left +1 self.node[i] -=1return i - self.N +1classSolution:
defreconstructQueue(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
impl Solution {
pubfnreconstruct_queue(mut people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
structSegmentTree {
n: usize,
node: Vec<i32>,
}
impl SegmentTree {
fnnew(n: usize) -> Self {
letmut N =1;
while N < n { N <<=1; }
letmut node = vec![0; (N <<1) -1];
for i in0..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 }
}
fninsert(&mut self, mut k: i32) -> usize {
letmut 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();
letmut st = SegmentTree::new(n);
letmut res = vec![vec![0, 0]; n];
for p in people {
let idx = st.insert(p[1]);
res[idx] = p;
}
res
}
}
⏰ 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.