Problem 33.7 · Greedy AlgorithmsMedium

Queue Reconstruction by Height

What it teaches: Sorting by a clever key: place tall people first, then insert shorter ones at their index.

Practise it on judges as “Queue Reconstruction by Height”.

The problem

people[i] = [h, k]: height h, and exactly k people in front are at least as tall. Reconstruct the queue.

Example 1

Input: [[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]]

Constraints

1 ≤ n ≤ 2000

Pattern clues in the wording

→ Counts of taller people in front

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        return people;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]	[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
2	people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]	[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

From slow to fast

Approaches

1. Sort and insert · O(n²) for list insertions

Sort and insert

Time O(n²) for list insertions Space O(n)

After sorting, inserting [h, k] at position k is correct: everyone already placed is at least as tall.

Approach 1

import java.util.*;

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(a[1], b[1]));
        List<int[]> queue = new ArrayList<>();
        for (int[] p : people) queue.add(p[1], p);
        return queue.toArray(new int[0][]);
    }
}

Verdict: Simple; n ≤ 2000.

Before you submit

Edge cases and common mistakes

Test these inputs

All same height
Single person

Mistakes people make

Sorting by height ascending (later insertions shift taller people's counts).

Interview

Follow-up questions

Can insertion be faster than O(n)?

Command Palette

The problem

Approaches

Sort and insert

Edge cases and common mistakes

Follow-up questions