Log inSign up
mediumLeetCodeNot Started

Queue Reconstruction by Height

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

You are given an array of people, people, where people[i] = [h_i, k_i] represents the i-th person of height h_i with exactly k_i other people in front who have a height greater than or equal to h_i.

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] = [h_j, k_j] is the j-th person in the queue (queue[0] is the person at the front of the queue).

Example 1 · Example 1: Six People:

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: Sorted order: [7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4].\n- Insert [7, 0] at 0 -> [[7, 0]]\n- Insert [7, 1] at 1 -> [[7, 0], [7, 1]]\n- Insert [6, 1] at 1 -> [[7, 0], [6, 1], [7, 1]]\n- Insert [5, 0] at 0 -> [[5, 0], [7, 0], [6, 1], [7, 1]]\n- Insert [5, 2] at 2 -> [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]\n- Insert [4, 4] at 4 -> [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

Constraints:

  • 1 <= people.length <= 2000
  • 0 <= h_i <= 106
  • 0 <= k_i < people.length
  • It is guaranteed that the queue can always be reconstructed.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand asymmetric dependency order (tallest to shortest).
  • Explain why inserting at index k maintains invariant correctness.
  • Implement the greedy reconstruction across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Reordering elements based on rank / count of predecessors.
  • Asymmetric visibility (taller affects shorter, but shorter does not affect taller).
  • Greedy insertion at explicit target index.

Algorithmic Decision Tree:

  • Sort (h, k): h descending, k ascending.
  • Insert each element at index k in result array.

Connected Patterns:

Count of Smaller Numbers After SelfCandyWiggle Sort II

1. Permutation Validation

Intuition

Generate every permutation of people and check if every person's height and k constraints are satisfied.

Algorithm

  1. Step 1: Generate all permutations of the array people.
  2. Step 2: For each permutation, verify if for every person i, exactly k_i people with height >= h_i precede them.
  3. Step 3: If valid, return that permutation.
  4. Step 4: Continue until valid queue is found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 bool isValid(const vector<vector<int>>& p) {
9 int n = p.size();
10 for (int i = 0; i < n; ++i) {
11 int count = 0;
12 for (int j = 0; j < i; ++j) {
13 if (p[j][0] >= p[i][0]) count++;
14 }
15 if (count != p[i][1]) return false;
16 }
17 return true;
18 }
19public:
20 vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
21 sort(people.begin(), people.end());
22 do {
23 if (isValid(people)) return people;
24 } while (next_permutation(people.begin(), people.end()));
25 return {};
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<vector<int>> people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
32 auto res = sol.reconstructQueue(people);
33 cout << "Reconstructed Queue:" << endl;
34 for (const auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
35 cout << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N! * N)
  • Space complexity: O(N)

2. Shortest First Empty Slot Allocation

Intuition

Sort people ascending by height and descending by k. Allocate each person to the (k + 1)-th empty slot in the output array.

Algorithm

  1. Step 1: Sort people ascending by h; if h is equal, sort descending by k.
  2. Step 2: Initialize an empty result array of size n with null / empty markers.
  3. Step 3: For each person [h, k]: count k empty slots, and place the person in the next available empty slot.
  4. Step 4: Return result array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
10 int n = people.size();
11 sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
12 if (a[0] == b[0]) return a[1] > b[1];
13 return a[0] < b[0];
14 });
15
16 vector<vector<int>> ans(n);
17 for (const auto& p : people) {
18 int count = p[1];
19 for (int i = 0; i < n; ++i) {
20 if (ans[i].empty()) {
21 if (count == 0) {
22 ans[i] = p;
23 break;
24 }
25 count--;
26 }
27 }
28 }
29
30 return ans;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<vector<int>> people = {{7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2}};
37 auto res = sol.reconstructQueue(people);
38 cout << "Reconstructed (Slot):" << endl;
39 for (const auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(N)

3. Tallest First Greedy Insertion

Intuition

Sort people descending by height and ascending by k. Insert each person into the output list directly at index k.

Algorithm

  1. Step 1: Sort people array descending by height person[0]. If heights are equal, sort ascending by person[1].
  2. Step 2: Initialize an empty list or vector ans.
  3. Step 3: For each person in sorted people: insert person at index person[1] in ans.
  4. Step 4: Return ans.

Interactive Trace for Queue Reconstruction

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Insert [7, 0] at index 0 and [7, 1] at index 1
Visual state
Values and pointers at this exact step
pointers
S
pos 0
pos 1
0
↑ placed
1
Check / comparison
Tallest elements placed first.
Decision / next transition
Queue has: [7, 0], [7, 1].
Why this step matters

Step 1: Insert [7, 0] at index 0 and [7, 1] at index 1. Queue = [[7, 0], [7, 1]].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
10 sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
11 if (a[0] == b[0]) return a[1] < b[1];
12 return a[0] > b[0];
13 });
14
15 vector<vector<int>> ans;
16 for (const auto& p : people) {
17 ans.insert(ans.begin() + p[1], p);
18 }
19
20 return ans;
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<vector<int>> people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
27 auto res = sol.reconstructQueue(people);
28 cout << "Reconstructed (Optimal):" << endl;
29 for (const auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
30 cout << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(N)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Permutation ValidationO(N! * N)O(N)Generate all N! permutations of the queue and verify each person's k condition.Testing all permutations.
2.Better — Shortest First Empty Slot AllocationO(N^2)O(N)Sort people ascending by height (shortest first) with k descending. Each person takes the (k+1)-th empty slot in the output array.Slot counting.
3.Optimal — Tallest First Greedy InsertionOptimalO(N^2)O(N)Sort people descending by height, then ascending by k. Insert each person into output list at index person[1].Array shifting during insertion.
Back to DSA Sheet