Queue Reconstruction by Height

Problem

Given people as [height, k] where k = number of people in front at least as tall, reconstruct the queue.

Constraints

• 1 ≤ n ≤ 2000

Approach — Greedy

This is a Greedy problem. The idea: make the locally best choice at each step, which provably builds up to the global optimum here. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log n) time.

Solution code

Python

class Solution:
    def reconstructQueue(self, people):
        people.sort(key=lambda p: (-p[0], p[1]))
        res = []
        for p in people:
            res.insert(p[1], p)
        return res

Java

import java.util.*;

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[]> out = new ArrayList<>();
        for (int[] p : people) out.add(p[1], p);
        return out.toArray(new int[0][]);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.