Skip to main content
Talentd

Queue Reconstruction by Height - Solution & Explanation

MediumArrayBinary Indexed TreeSegment TreeSorting11 min readAsked at: Amazon, Meta, Google +2
Practice this problem

Problem Statement

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 <= 2000
  • 0 <= hi <= 106
  • 0 <= 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.

This C solution sorts the list with a custom comparator and then builds the resulting queue by inserting each person at their k-th index. The qsort is used for sorting the list based on the height in descending order and the k-value in ascending order. We use an auxiliary array to store the reconstructed queue, shifting elements as needed during insertion to maintain order.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to the potential element shifting during insertion.
Space Complexity: O(1) additional space required.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Insertion Approach

Time Complexity: O(n^2) due to the potential element shifting during insertion.
Space Complexity: O(1) additional space required.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Sorting + List InsertionO(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 AllocationO(n log n)O(n)Alternative to BIT when practicing advanced range query structures.

Video Solution

Queue Reconstruction by Height | Leetcode #406 • Techdose • 29,919 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Queue Reconstruction by Height with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count of Smaller Numbers After Self

Next

Reward Top K Students