Queue Reconstruction by Height — Problem & Solution
Queue Reconstruction by Height solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Queue Reconstruction by Height is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Binary Indexed Tree
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array people where people[i] = [h, k] means the i-th person has height h and that exactly k people of height at least h stand in front of them.
Reconstruct and return the queue as an array in the same [h, k] format, ordered front to back.
Example 1
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]]
Example 2
Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
Example 3
Input: people = [[1,0]]
Output: [[1,0]]
Constraints
1 <= people.length <= 300 <= h <= 1000 <= k < people.lengthThe queue is guaranteed to be reconstructible.
Hints for Queue Reconstruction by Height
Hint 1
Place the tallest people first: shorter people inserted later are invisible to them, so their
knever changes.Hint 2
Sort by height descending, breaking ties by
kascending.Hint 3
Then insert each person at index
k— with only taller-or-equal people already placed, indexkis exactly the right spot.
How to solve Queue Reconstruction by Height
Place tallest first: shorter people inserted later are invisible to them. Sort by height descending (ties by k ascending) and insert each person at index k.
Approach
- Sort by
(-h, k). - For each person, insert at position
kin the output list.
Why it works
When a person is inserted, everyone already placed is at least as tall, so the count of taller-or-equal people in front is exactly the insertion index. Later, shorter insertions do not change that count.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Ties must break by
kascending so equal heights are inserted in the right order.
Reference solution
Python
def reconstructQueue(people):
ordered = sorted(people, key=lambda p: (-p[0], p[1]))
out = []
for person in ordered:
out.insert(person[1], person)
return outJava
public static int[][] reconstructQueue(int[][] people) {
int[][] s = people.clone();
Arrays.sort(s, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
List<int[]> out = new ArrayList<>();
for (int[] p : s) out.add(p[1], new int[]{p[0], p[1]});
return out.toArray(new int[0][]);
}C++
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
vector<vector<int>> s = people;
sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] > b[0];
return a[1] < b[1];
});
vector<vector<int>> out;
for (const auto& p : s) {
out.insert(out.begin() + p[1], vector<int>{p[0], p[1]});
}
return out;
}JavaScript
var reconstructQueue = function(people) {
const sorted = people.slice().sort(function(a, b) {
return b[0] !== a[0] ? b[0] - a[0] : a[1] - b[1];
});
const out = [];
for (let i = 0; i < sorted.length; i++) {
out.splice(sorted[i][1], 0, sorted[i]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms