Queue Reconstruction by Height
Queue Reconstruction by Height is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (fenwick tree over empty seats), runs in O(n log n) time and O(n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (shortest first into empty seats) up.
Problem
A group of people stood in a line, but the line got shuffled. Each person is described by a pair people[i] = [h, k]: h is their height and k is how many people standing in front of them in the original line were at least as tall as they are (height >= h).
Rebuild the line: return the pairs arranged in the order they originally stood, so that the k of every pair is correct. The input always comes from some valid line.
Examples
Example 1
- Input
people = [[7, 1], [4, 4], [5, 0], [6, 1], [7, 0], [5, 1]]- Output
[[5, 0], [5, 1], [7, 0], [6, 1], [4, 4], [7, 1]]- Why
- Check [4, 4]: the four people ahead of it (heights 5, 5, 7, 6) are all at least 4 tall. Every other pair checks out the same way.
Example 2
- Input
people = [[2, 1], [1, 1], [3, 0]]- Output
[[3, 0], [1, 1], [2, 1]]- Why
- Height 3 has nobody ahead, height 1 has one taller person ahead, and height 2 has exactly one person (the 3) who is at least as tall.
Constraints
1 <= people.length <= 20000 <= h_i <= 10^60 <= k_i < people.length- The input is guaranteed to describe some valid queue.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (shortest first into empty seats) | O(n²) | O(n) |
| Tallest first, insert at index k | O(n²) | O(n) |
| Optimal (Fenwick tree over empty seats) | O(n log n) | O(n) |
1Brute force (shortest first into empty seats)
O(n²)Sorting is O(n log n); each of the n placements scans up to n seats.O(n)The result array.Seat people from shortest to tallest. When a person is seated, every empty seat will later be filled by someone at least as tall, and every filled seat holds someone shorter (or of equal height but larger k). So a person with count k goes into the (k + 1)-th empty seat from the front. For equal heights, seat the larger k first so the earlier one counts as an empty seat.
- Sort by height ascending, and by k descending for equal heights.
- Create an array of n empty seats.
- For each person, scan from the front, skip k empty seats and place them in the next empty one.
class Solution {
public int[][] reconstructQueue(int[][] people) {
int n = people.length;
Arrays.sort(people, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
int[][] res = new int[n][];
for (int[] p : people) {
int skip = p[1];
for (int i = 0; i < n; i++) {
if (res[i] == null) {
if (skip == 0) {
res[i] = p;
break;
}
skip--;
}
}
}
return res;
}
}class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
n = len(people)
res = [None] * n
for h, k in sorted(people, key=lambda p: (p[0], -p[1])):
skip = k
for i in range(n):
if res[i] is None:
if skip == 0:
res[i] = [h, k]
break
skip -= 1
return resclass Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
int n = people.size();
sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
});
vector<vector<int>> res(n);
vector<bool> used(n, false);
for (auto& p : people) {
int skip = p[1];
for (int i = 0; i < n; i++) {
if (!used[i]) {
if (skip == 0) {
res[i] = p;
used[i] = true;
break;
}
skip--;
}
}
}
return res;
}
};function reconstructQueue(people) {
const n = people.length;
people.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
const res = new Array(n).fill(null);
for (const p of people) {
let skip = p[1];
for (let i = 0; i < n; i++) {
if (res[i] === null) {
if (skip === 0) {
res[i] = p;
break;
}
skip--;
}
}
}
return res;
}2Tallest first, insert at index k
O(n²)Each list insertion can shift up to n elements.O(n)The output list.Process people from tallest to shortest (smaller k first among equal heights). When a person is processed, everyone already in the line is at least as tall, so they belong exactly at index k of the current line. People inserted later are shorter, so they never change the counts of anyone already placed.
- Sort by height descending, and by k ascending for equal heights.
- Start with an empty list.
- For each person, insert them at index k.
- Return the list.
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
List<int[]> line = new ArrayList<>();
for (int[] p : people) {
line.add(p[1], p);
}
return line.toArray(new int[0][]);
}
}class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
line = []
for p in sorted(people, key=lambda p: (-p[0], p[1])):
line.insert(p[1], p)
return lineclass 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[0] > b[0] : a[1] < b[1];
});
vector<vector<int>> line;
for (auto& p : people) {
line.insert(line.begin() + p[1], p);
}
return line;
}
};function reconstructQueue(people) {
people.sort((a, b) => a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1]);
const line = [];
for (const p of people) {
line.splice(p[1], 0, p);
}
return line;
}3Optimal (Fenwick tree over empty seats)
O(n log n)Sorting is O(n log n), and each search and update on the Fenwick tree is O(log n).O(n)The Fenwick tree and the result array.Speed up the first idea. Keep a Fenwick (binary indexed) tree where each seat counts 1 while it is empty. Finding the (k + 1)-th empty seat is a prefix-sum search, which a Fenwick tree answers in O(log n) by descending through powers of two; filling a seat is a point update of -1.
- Sort by height ascending, and by k descending for equal heights.
- Build a Fenwick tree over n seats, all set to 1 (tree[i] = i & -i).
- For each person, walk down from the largest power of two <= n: move right while the block's count is still less than the remaining k + 1, subtracting it. The seat is pos + 1.
- Place the person in that seat and add -1 at that position.
class Solution {
public int[][] reconstructQueue(int[][] people) {
int n = people.length;
Arrays.sort(people, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
int[] tree = new int[n + 1];
for (int i = 1; i <= n; i++) tree[i] = i & -i;
int top = 1;
while (top * 2 <= n) top *= 2;
int[][] res = new int[n][];
for (int[] p : people) {
int pos = 0, rem = p[1] + 1;
for (int step = top; step > 0; step >>= 1) {
if (pos + step <= n && tree[pos + step] < rem) {
pos += step;
rem -= tree[pos];
}
}
res[pos] = p;
for (int i = pos + 1; i <= n; i += i & -i) tree[i]--;
}
return res;
}
}class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
n = len(people)
tree = [0] * (n + 1)
for i in range(1, n + 1):
tree[i] = i & -i
top = 1
while top * 2 <= n:
top *= 2
res = [None] * n
for h, k in sorted(people, key=lambda p: (p[0], -p[1])):
pos, rem, step = 0, k + 1, top
while step > 0:
if pos + step <= n and tree[pos + step] < rem:
pos += step
rem -= tree[pos]
step >>= 1
res[pos] = [h, k]
i = pos + 1
while i <= n:
tree[i] -= 1
i += i & -i
return resclass Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
int n = people.size();
sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
});
vector<int> tree(n + 1, 0);
for (int i = 1; i <= n; i++) tree[i] = i & -i;
int top = 1;
while (top * 2 <= n) top *= 2;
vector<vector<int>> res(n);
for (auto& p : people) {
int pos = 0, rem = p[1] + 1;
for (int step = top; step > 0; step >>= 1) {
if (pos + step <= n && tree[pos + step] < rem) {
pos += step;
rem -= tree[pos];
}
}
res[pos] = p;
for (int i = pos + 1; i <= n; i += i & -i) tree[i]--;
}
return res;
}
};function reconstructQueue(people) {
const n = people.length;
people.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
const tree = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) tree[i] = i & -i;
let top = 1;
while (top * 2 <= n) top *= 2;
const res = new Array(n);
for (const p of people) {
let pos = 0, rem = p[1] + 1;
for (let step = top; step > 0; step >>= 1) {
if (pos + step <= n && tree[pos + step] < rem) {
pos += step;
rem -= tree[pos];
}
}
res[pos] = p;
for (let i = pos + 1; i <= n; i += i & -i) tree[i]--;
}
return res;
}Edge cases to test
- A single person
- Everyone has the same height: they line up by k
- Equal heights count as "at least as tall", so ties change k
- Input already in queue order, or in reverse
Hints
Hint 1
Look at the shortest person. Everybody else is at least as tall, so k says exactly how many seats sit in front of them.
Hint 2
Alternatively, place the tallest people first: shorter people inserted later are invisible to them, so inserting later never breaks an earlier count.
Hint 3
Sort by height descending (k ascending on ties) and insert each person at index k.
FAQ
What is the best time complexity for Queue Reconstruction by Height?
Optimal (Fenwick tree over empty seats) runs in O(n log n) time and O(n) extra space. Sorting is O(n log n), and each search and update on the Fenwick tree is O(log n).
Which pattern does Queue Reconstruction by Height use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Queue Reconstruction by Height?
Yes. Brute force (shortest first into empty seats) takes O(n²) time and O(n) space. Seat people from shortest to tallest.
Which edge cases should I test for Queue Reconstruction by Height?
A single person; Everyone has the same height: they line up by k; Equal heights count as "at least as tall", so ties change k; Input already in queue order, or in reverse.