Queue Reconstruction by Height

Medium
343.

Queue Reconstruction by Height

Queue Reconstruction by Height is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

You are given an array people where people[i] = [h, k] means the i-th person has height h and that exactly k people of height at least h stand in front of them.

Reconstruct and return the queue as an array in the same [h, k] format, ordered front to 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]]

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

Example 3

Input
people = [[1,0]]
Output
[[1,0]]

Constraints

  • 1 <= people.length <= 30
  • 0 <= h <= 100
  • 0 <= k < people.length
  • The queue is guaranteed to be reconstructible.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Queue Reconstruction by Height — Problem & Solution

Queue Reconstruction by Height solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Queue Reconstruction by Height is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given an array people where people[i] = [h, k] means the i-th person has height h and that exactly k people of height at least h stand in front of them.

Reconstruct and return the queue as an array in the same [h, k] format, ordered front to 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]]

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

Example 3

Input: people = [[1,0]]
Output: [[1,0]]

Constraints

  • 1 <= people.length <= 30
  • 0 <= h <= 100
  • 0 <= k < people.length
  • The queue is guaranteed to be reconstructible.

Hints for Queue Reconstruction by Height

  1. Hint 1

    Place the tallest people first: shorter people inserted later are invisible to them, so their k never changes.

  2. Hint 2

    Sort by height descending, breaking ties by k ascending.

  3. Hint 3

    Then insert each person at index k — with only taller-or-equal people already placed, index k is exactly the right spot.

How to solve Queue Reconstruction by Height

Place tallest first: shorter people inserted later are invisible to them. Sort by height descending (ties by k ascending) and insert each person at index k.

Approach

  1. Sort by (-h, k).
  2. For each person, insert at position k in the output list.

Why it works

When a person is inserted, everyone already placed is at least as tall, so the count of taller-or-equal people in front is exactly the insertion index. Later, shorter insertions do not change that count.

Complexity

  • Time — O(n²)
  • Space — O(n)

Pitfalls

  • Ties must break by k ascending so equal heights are inserted in the right order.

Reference solution

Python

def reconstructQueue(people):
    ordered = sorted(people, key=lambda p: (-p[0], p[1]))
    out = []
    for person in ordered:
        out.insert(person[1], person)
    return out

Java

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

C++

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

JavaScript

var reconstructQueue = function(people) {
    const sorted = people.slice().sort(function(a, b) {
        return b[0] !== a[0] ? b[0] - a[0] : a[1] - b[1];
    });
    const out = [];
    for (let i = 0; i < sorted.length; i++) {
        out.splice(sorted[i][1], 0, sorted[i]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms