Queue Reconstruction by Height

medium array greedy sorting

Problem

You are given a list of people as pairs [h, k] meaning a person of height h has k taller-or-equal people in front of them. Reconstruct and return the queue as a list of [h, k] pairs.

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

Sort by height ↓ then k ↑; insert each at position k — shorter inserts later never violate prior k counts.

people (e.g. 7,0; 4,4; 7,1; 5,0)

def reconstruct_queue(people):
    people.sort(key=lambda p: (-p[0], p[1]))
    out = []
    for h, k in people:
        out.insert(k, [h, k])
    return out

function reconstructQueue(people) {
  people.sort((a, b) => b[0] - a[0] || a[1] - b[1]);
  const out = [];
  for (const [h, k] of people) out.splice(k, 0, [h, k]);
  return out;
}

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

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), [](auto& a, auto& b) {
        return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];
    });
    vector<vector<int>> out;
    for (auto& p : people) out.insert(out.begin() + p[1], p);
    return out;
}

Explanation

Each person is a pair [h, k] meaning "k people at least as tall as me stand in front of me." The clever order is to place the tallest people first, because shorter people added later never affect a taller person's count.

So we sort by height descending, and for equal heights by k ascending. Then we build the answer by inserting each person at index k.

Why does that work? When we insert someone of height h, everyone already in the queue is taller or equal to them (they were placed earlier). So putting them at index k guarantees exactly k taller-or-equal people end up in front — precisely what k demands. Later shorter inserts slide in without breaking that, since they are not counted by taller people.

Example: from [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] we sort to [7,0],[7,1],[6,1],[5,0],[5,2],[4,4]. Inserting each at its k builds [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]].

The tall-first rule plus insert-at-k is the whole trick; it turns a tricky constraint problem into simple list insertions.

Time: O(n²) Space: O(n)