Queue Reconstruction by Height solution and explanation
Google
9 more videos on this problem
Queue Reconstruction by Height | Leetcode #406Techdose · 15:30 · 29K views
Queue Reconstruction by Height | LeetCode 406 | C++, Java, PythonKnowledge Center · 20:48 · 10K views
Queue Reconstruction By Height Solution - Leetcode 406 (Arabic)Ahmed Ali · 1:18:57 · 4K views
Leetcode 406 Queue Reconstruction by Height | 👉🏼 Coding Decoded SDE SheetCoding Decoded · 14:12 · 2K views
Leetcode - Queue Reconstruction by Height (Python)Timothy H Chang · 6:28 · 1K views
406. Queue Reconstruction by HeightTech Adora by Nivedita · 12:16 · 1K views
406. Queue Reconstruction by Height (updated video in description) (Leetcode Medium)Programming Live with Larry · 32:23 · 1K views
LeetCode 406. Queue Reconstruction by HeightHappy Coding · 15:30 · 1K views
Queue Reconstruction by Height | LeetCode 406 | Programming TutorialsProgramming Tutorials · 13:36 · 951 views
Queue Reconstruction by Height | Java | LeetCode - Medium - 406 | The Code MateThe Code Mate · 13:25 · 904 views
The problem
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 exactly ki 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 array people. 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).
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]] Explanation: Person 0 has height 5 with no other people taller or the same height in front. Person 1 has height 7 with no other people taller or the same height in front. Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1. Person 3 has height 6 with one person taller or the same height in front, which is person 1. Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3. Person 5 has height 7 with 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:
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]]
Constraints:
1 <= people.length <= 20000 <= hi <= 1060 <= ki < people.length- It is guaranteed that the queue can be reconstructed.
Approach overview
Problem Overview: You are given people represented as [h, k], where h is height and k is the number of people in front who have height greater than or equal to h. Reconstruct the original queue so every person’s k value is satisfied.
Approach 1: Greedy Sorting + List Insertion (O(n2) time, O(n) space)
The key observation: taller people do not get affected by shorter people placed later. Sort the array by height in descending order, and if heights are equal, sort by k ascending. Then iterate through the sorted list and insert each person at index k in the result list. Because all previously inserted people are taller or equal height, inserting at position k guarantees exactly k valid people ahead. Each insertion into a list costs O(n), giving overall O(n^2) time with O(n) extra space.
This approach relies heavily on sorting and array insertion mechanics. Once the ordering rule is understood, the implementation becomes short and reliable.
Approach 2: Binary Indexed Tree Placement (O(n log n) time, O(n) space)
An alternative uses a Binary Indexed Tree to track empty positions in the queue. First sort people by height ascending and by k ascending. Then treat the queue as empty slots. For each person, locate the position where exactly k taller-or-equal people will appear in front by querying the BIT for the (k+1)-th empty slot. Update the tree when a slot is filled. This reduces insertion cost from O(n) to O(log n).
The BIT stores prefix sums representing available positions. Each query finds the index whose cumulative count equals a target slot number. This keeps the total complexity at O(n log n) with O(n) space.
Approach 3: Segment Tree Slot Allocation (O(n log n) time, O(n) space)
A segment tree can replace the BIT for managing empty positions. Each node stores the number of available slots in its range. During reconstruction, perform a query to locate the index representing the required free slot and update the tree once that position is used. The complexity matches the BIT approach but with a slightly heavier constant factor.
Recommended for interviews: The greedy sorting plus insertion approach is what most interviewers expect. It demonstrates that you recognized the core ordering insight: place taller people first so shorter ones never invalidate earlier constraints. Mentioning the BIT or segment tree optimization shows deeper algorithm knowledge, but the greedy O(n2) method is usually sufficient and easier to implement under interview pressure.
Approach 1: Greedy Insertion Approach
In this approach, we first sort the array of people. The sorting criteria should be descending order of height and ascending order of the number of people in front for the same height. After sorting, we iterate through the list and insert each person into a new list at the index corresponding to the number of people in front of them. This ensures that each person is placed correctly with regard to the number of taller or equally tall people in front.
def reconstructQueue(people):
people.sort(key=lambda x: (-x[0], x[1]))
queue = []
for person in people:
queue.insert(person[1], person)
return queue
people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
result = reconstructQueue(people)
for person in result:
print(person)import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : b[0] - a[0]);
List<int[]> result = new LinkedList<>();
for (int[] p : people) {
result.add(p[1], p);
}
return result.toArray(new int[people.length][2]);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
int[][] result = sol.reconstructQueue(people);
for (int[] person : result) {
System.out.print("[" + person[0] + ", " + person[1] + "] ");
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
});
vector<vector<int>> queue;
for (auto& person : people) {
queue.insert(queue.begin() + person[1], person);
}
return queue;
}
int main() {
vector<vector<int>> people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
vector<vector<int>> result = reconstructQueue(people);
for (auto& person : result) {
cout << "[" << person[0] << ", " << person[1] << "] ";
}
return 0;
}function reconstructQueue(people) {
people.sort((a, b) => {
return a[0] === b[0] ? a[1] - b[1] : b[0] - a[0];
});
const queue = [];
for (let person of people) {
queue.splice(person[1], 0, person);
}
return queue;
}
const people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]];
const result = reconstructQueue(people);
console.log(result);#include <stdio.h>
#include <stdlib.h>
// Comparator function for sorting
int compare(const void* a, const void* b) {
int* personA = *(int**)a;
int* personB = *(int**)b;
if (personA[0] != personB[0])
return personB[0] - personA[0];
return personA[1] - personB[1];
}
void queueReconstruction(int** people, int peopleSize, int* peopleColSize, int** returnColumnSizes) {
qsort(people, peopleSize, sizeof(int*), compare);
int** queue = malloc(sizeof(int*) * peopleSize);
int queueSize = 0;
for (int i = 0; i < peopleSize; i++) {
int k = people[i][1];
// Shift elements if necessary
for (int j = queueSize; j > k; j--) {
queue[j] = queue[j - 1];
}
queue[k] = people[i];
queueSize++;
}
*returnColumnSizes = (int*)malloc(sizeof(int) * peopleSize);
for (int i = 0; i < peopleSize; i++) {
(*returnColumnSizes)[i] = 2;
}
// Display result (example for demonstration)
printf("[");
for (int i = 0; i < peopleSize; i++) {
printf("[%d, %d]", queue[i][0], queue[i][1]);
if (i < peopleSize - 1) printf(", ");
}
printf("]");
free(queue);
}
int main() {
int arr[][2] = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
int* people[] = {arr[0], arr[1], arr[2], arr[3], arr[4], arr[5]};
int peopleColSize[] = {2, 2, 2, 2, 2, 2};
int* returnColumnSizes;
queueReconstruction(people, 6, peopleColSize, &returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] ReconstructQueue(int[][] people) {
Array.Sort(people, (a, b) => {
if (a[0] != b[0]) return b[0] - a[0];
return a[1] - b[1];
});
List<int[]> queue = new List<int[]>();
foreach (var person in people) {
queue.Insert(person[1], person);
}
return queue.ToArray();
}
public static void Main() {
Solution sol = new Solution();
int[][] people = new int[][] {
new int[] { 7, 0 }, new int[] { 4, 4 }, new int[] { 7, 1 },
new int[] { 5, 0 }, new int[] { 6, 1 }, new int[] { 5, 2 }
};
int[][] result = sol.ReconstructQueue(people);
foreach (var person in result) {
Console.Write("[" + string.Join(", ", person) + "] ");
}
}
}This Python solution sorts the input list with a lambda function that defines the sorting criteria: height is sorted in descending order and the k-value in ascending order. After sorting, each person is inserted into the resulting list at the index specified by their k-value.
Time Complexity: O(n^2) for the list insertions.
Space Complexity: O(n) for the output list.
Approach 2: Default Approach
func reconstructQueue(people [][]int) [][]int {
sort.Slice(people, func(i, j int) bool {
a, b := people[i], people[j]
return a[0] > b[0] || a[0] == b[0] && a[1] < b[1]
})
var ans [][]int
for _, p := range people {
i := p[1]
ans = append(ans[:i], append([][]int{p}, ans[i:]...)...)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Insertion Approach | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Sorting + List Insertion | O(n^2) | O(n) | Standard interview solution. Simple logic and short implementation. |
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) | Useful when optimizing insert operations by tracking empty slots. |
| Segment Tree Slot Allocation | O(n log n) | O(n) | Alternative to BIT when practicing advanced range query structures. |
Frequently asked questions
Is Queue Reconstruction by Height easy or hard?
The problem is rated Medium on LeetCode. The challenge lies in recognizing the greedy ordering strategy. Once you realize taller people should be placed first, the implementation becomes straightforward.
How to solve Queue Reconstruction by Height in O(n log n)?
Use a Binary Indexed Tree or Segment Tree to track available positions in the queue. After sorting people by height and k, query the structure to find the correct empty slot for each person. Each placement and update takes O(log n), leading to total O(n log n) time.
What is the best approach for Queue Reconstruction by Height?
The most common solution is the greedy sorting and insertion approach. Sort people by height descending and k ascending, then insert each person at index k in the result list. This guarantees the correct number of taller or equal-height people ahead. The time complexity is O(n^2) due to list insertion.
Is Queue Reconstruction by Height asked at Google/Amazon/Meta?
Queue Reconstruction by Height is a common medium-level interview problem that appears in coding interviews at large tech companies. Variations of the problem testing greedy reasoning and sorting have been reported in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Queue Reconstruction by Height?
The standard solution mainly uses arrays or lists combined with sorting. Optimized solutions can use advanced structures such as a Binary Indexed Tree (Fenwick Tree) or Segment Tree to efficiently locate available positions in the queue.
What is the time complexity of Queue Reconstruction by Height?
The typical greedy insertion solution runs in O(n^2) time because inserting into a list shifts elements. Sorting costs O(n log n) but insertion dominates. Optimized versions using Binary Indexed Tree or Segment Tree reduce the complexity to O(n log n).
Queue Reconstruction by Height Python or Java solution approach?
Both Python and Java implementations follow the same greedy idea: sort by height descending and k ascending, then insert each person at index k in a list. Python uses list.insert(), while Java typically uses ArrayList.add(index, element). The algorithm remains O(n^2).