Queue Reconstruction by Height
Medium · Arrays & Hashing · Explanation and code example
Binary Indexed Tree (Fenwick Tree)
How it works
We can eliminate the explicit binary search by leveraging the BIT's structure directly. Instead of querying prefix sums and binary searching, we walk down the BIT's implicit tree structure, using the most significant bit to guide our traversal. This finds the (k + 1)th empty slot in O(log n) time with a single pass.
Steps
- Sort people by height ascending, then by
kdescending for ties. - Initialize a BIT with all positions marked as available.
- For each person:
- Use bit manipulation to traverse the BIT directly, finding the position with exactly
kavailable slots before it. - Place the person at the found position.
- Update the BIT to mark that slot as filled.
- Use bit manipulation to traverse the BIT directly, finding the position with exactly
- Return the result array.
Complexity
- Time complexity:
O(nlog n) - Space complexity:
O(n)
Things to watch for
Incorrect Sorting Order for Same Heights
When two people have the same height, they must be sorted by k-value in the correct secondary order. For descending height approach, sort by k ascending (smaller k first). Reversing this order causes insertions to shift previously placed same-height people incorrectly.
Using Wrong Insertion Index
The k-value represents how many people with height >= current person's height should be in front. When processing tallest-first, k directly gives the insertion index since all previously placed people are at least as tall. Misinterpreting k as the count of taller (not taller-or-equal) people leads to wrong placements.
Modifying List While Iterating
Some implementations attempt to build the queue by modifying the input array in place or iterating while inserting. This causes elements to shift unexpectedly. Always use a separate result list and insert into it, or use the ascending height approach with pre-allocated slots.
Python code example
from typing import List
import math
class BIT:
def __init__(self, N):
self.n = N + 1
self.tree = [0] * self.n
for i in range(self.n - 1):
self.update(i, 1)
def update(self, index, val):
index += 1
while index < self.n:
self.tree[index] += val
index += index & -index
def getIdx(self, cnt, MSB):
idx = 0
while MSB:
nxtIdx = idx + MSB
if nxtIdx < self.n and cnt >= self.tree[nxtIdx]:
idx = nxtIdx
cnt -= self.tree[nxtIdx]
MSB >>= 1
return idx
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
n = len(people)
people.sort(key=lambda x: (x[0], -x[1]))
res = [[] for _ in range(n)]
bit = BIT(n)
MSB = 1 << int(math.log(n, 2))
for p in people:
idx = bit.getIdx(p[1], MSB)
res[idx] = p
bit.update(idx, -1)
return res
C++ code example
class BIT {
vector<int> tree;
int n;
public:
BIT(int N) {
n = N + 1;
tree.resize(n, 0);
for (int i = 0; i < n - 1; i++) {
update(i, 1);
}
}
void update(int index, int val) {
index++;
while (index < n) {
tree[index] += val;
index += index & -index;
}
}
int getIdx(int cnt, int MSB) {
int idx = 0;
while (MSB != 0) {
int nxtIdx = idx + MSB;
if (nxtIdx < n && cnt >= tree[nxtIdx]) {
idx = nxtIdx;
cnt -= tree[nxtIdx];
}
MSB >>= 1;
}
return idx;
}
};
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
int n = people.size();
sort(people.begin(), people.end(), [](auto& a, auto& b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
});
vector<vector<int>> res(n, vector<int>());
BIT bit(n);
int MSB = 1 << (31 - __builtin_clz(n));
for (const auto& p : people) {
int idx = bit.getIdx(p[1], MSB);
res[idx] = p;
bit.update(idx, -1);
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.