LeetCode #406 — MEDIUM

Queue Reconstruction by Height

Move from brute-force thinking to an efficient approach using array strategy.

The 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] = [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 attributes of the j^th 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 <= h_i <= 10⁶
0 <= k_i < people.length
It is guaranteed that the queue can be reconstructed.

Step 01

Brute Force Baseline

Problem summary: 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).

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Segment Tree

Example 1

[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

Example 2

[[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

Core Insight

What unlocks the optimal approach

What can you say about the position of the shortest person? </br> If the position of the shortest person is <i>i</i>, how many people would be in front of the shortest person?
Once you fix the position of the shortest person, what can you say about the position of the second shortest person?

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #406: Queue Reconstruction by Height
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[]> ans = new ArrayList<>(people.length);
        for (int[] p : people) {
            ans.add(p[1], p);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

// Accepted solution for LeetCode #406: Queue Reconstruction by Height
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
}

# Accepted solution for LeetCode #406: Queue Reconstruction by Height
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        ans = []
        for p in people:
            ans.insert(p[1], p)
        return ans

// Accepted solution for LeetCode #406: Queue Reconstruction by Height
struct Solution;

use std::cmp::Reverse;

type People = (Reverse<i32>, i32);

impl Solution {
    fn reconstruct_queue(people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut people: Vec<People> = people.iter().map(|v| (Reverse(v[0]), v[1])).collect();
        people.sort_unstable();
        let mut res = vec![];
        for p in people {
            res.insert(p.1 as usize, vec![(p.0).0, p.1]);
        }
        res
    }
}

#[test]
fn test() {
    let people = vec_vec_i32![[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]];
    let res = vec![[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]];
    assert_eq!(Solution::reconstruct_queue(people), res);
}

// Accepted solution for LeetCode #406: Queue Reconstruction by Height
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #406: Queue Reconstruction by Height
// 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[]> ans = new ArrayList<>(people.length);
//         for (int[] p : people) {
//             ans.add(p[1], p);
//         }
//         return ans.toArray(new int[ans.size()][]);
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n + q log n)

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n × q) time

O(1) space

For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.

SEGMENT TREE

O(n + q log n) time

O(n) space

Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.

Shortcut: Build O(n), query/update O(log n) each. When you need both range queries AND point updates.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.