What is the brute force approach and complexity for Queue Reconstruction by Height?

Try every arrangement of the people; keep the first one where every k is right with time complexity O(N! · N²) and space complexity O(N).

What is the optimal approach and complexity for Queue Reconstruction by Height?

Sort by height (tallest first, then k ascending); insert each person at index k with optimal time complexity O(N²) and space complexity O(N).

How do you identify the pattern for Queue Reconstruction by Height?

Look for key signals in the prompt: "k people in front who are at least as tall" indicates The count looks only forward, and only at people at least as tall.; "rebuild the queue" indicates Every person gets one place in the final line, and the answer is those places.; "the queue can be reconstructed" indicates The input is always valid, so any insert that follows the rule is correct..

Queue Reconstruction by Height

Medium·LeetCode #406 Pro OnlyMedium

LeetCode

Problem Statement

People stand in a line, but the list you are given is shuffled. Each person is written as [h, k]:

h is the person's height.
k is how many people in front of them are at least as tall as them.

Rebuild the line from front to back and return it.

Input

people: a list of [h, k] pairs, in random order.

Output

The rebuilt line as a list of [h, k] pairs, from the front of the line to the 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]]

The person [4,4] has four people at least as tall in front: [5,0], [7,0], [5,2] and [6,1]. The person [7,1] has one person at least as tall in front: [7,0].

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]]

The person [1,4] has four people in front: [4,0], [5,0], [2,2] and [3,2], and all are at least 1 tall.

Constraints

• 1 ≤ people.length ≤ 2000
• 0 ≤ h ≤ 10^6
• 0 ≤ k < people.length
• The list always comes from a real line, so a valid answer exists.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“k people in front who are at least as tall”

→ The count looks only forward, and only at people at least as tall.

“rebuild the queue”

→ Every person gets one place in the final line, and the answer is those places.

“the queue can be reconstructed”

→ The input is always valid, so any insert that follows the rule is correct.

Approach Complexity Ladder

Brute Force — try every order and checkO(N! · N²)O(N)

Try every arrangement of the people; keep the first one where every k is right

Optimal — sort tallest first, insert each person at index kO(N²)O(N)

Sort by height (tallest first, then k ascending); insert each person at index k

Brute Force Intuition

There are N! orders of the people. For each order, check every position: count how many people in front are at least as tall, and compare that with k. Return the first order that passes every check.

Recognition rule for this sub-pattern:

Sort by the right key (ratio, deadline, height); argue that swapping any two out-of-order items cannot help.

Remember this · Greedy

Trigger

Maximise count / minimise cost with a natural "best next step", sorting makes the choice obvious, reachability.

Think

Is there a choice I can always make safely without looking ahead?

Key question

Why can't the greedy choice be worse than the optimal one? (Try to break it with a small example.)

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture