Queue Reconstruction by Height — Greedy Sort and Insert [LeetCode 406]

Problem Statement#

LeetCode 406 — Queue Reconstruction by Height (Medium)

You are given an array of people people, where people[i] = [hi, ki]. Each hi is the height of the i-th person and ki is the number of people in front of the i-th person who have a height greater than or equal to hi. Reconstruct and return the queue that is represented by the input array. The returned queue should be formatted as an array queue where queue[j] = [hj, kj] is the attributes of the j-th person in the queue (0-indexed).

Constraints:

• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• It is guaranteed to have a valid queue as the input.

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]]
Explanation: Person [5,0]: height 5, 0 people of height >= 5 in front. Correct.
             Person [7,0]: height 7, 0 people of height >= 7 in front. Correct.
             ... and so on.

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

Why This Problem Matters#

Queue Reconstruction by Height is a classic example of a greedy algorithm with a non-obvious sort key. The trick — sort taller people first, then insert each person at their specified k position — is elegant and counterintuitive, which makes it a favourite interview question at Google, Amazon, and Meta.

The problem tests several skills simultaneously: recognising that a complex reconstruction problem can be decomposed into a simple greedy, understanding why inserting in a specific order maintains the invariant, and implementing list insertion efficiently. The O(n^2) insertion approach is the expected solution, but follow-up questions often probe whether you know the O(n log n) BIT/segment tree alternative.

This problem frequently appears as a medium-difficulty challenge after easier greedy problems in an interview session. Its value lies in the mental leap required: rather than thinking "how do I place everyone at once," you think "in what order should I place people so each placement is trivially correct?"

The Core Insight#

Key observation: If we process taller people first, then when we insert a shorter person at position k, all people already in the queue are at least as tall as the current person. Therefore, inserting the shorter person at position k gives them exactly k people at least as tall in front — their k value is automatically satisfied.

Why does this work? Because shorter people are "invisible" to taller people in terms of the k count. When a tall person is inserted, they only count people of their height or taller in front of them. Any shorter people inserted afterward do not affect the tall person's k value.

Algorithm:

1. Sort people by height descending. For ties, sort by k ascending (so people with fewer required taller people in front come first — they get inserted earlier and claim earlier positions).
2. Insert each person at index k in the result list.

The insertion at position k means the person is placed after exactly k people already in the queue, all of whom are at least as tall. This satisfies their constraint by construction.

Visual Dry Run#

Input: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
 
After sorting (height desc, k asc):
[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
 
Insert step by step:
 
[7,0]: insert at index 0 → result = [[7,0]]
[7,1]: insert at index 1 → result = [[7,0],[7,1]]
[6,1]: insert at index 1 → result = [[7,0],[6,1],[7,1]]
[5,0]: insert at index 0 → result = [[5,0],[7,0],[6,1],[7,1]]
[5,2]: insert at index 2 → result = [[5,0],[7,0],[5,2],[6,1],[7,1]]
[4,4]: insert at index 4 → result = [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
 
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]  ✓

Verification of result:

Solution (Optimal)#

class Solution:
    def reconstructQueue(self, people: list[list[int]]) -> list[list[int]]:
        # Sort: taller first (desc height), then by k ascending for ties
        people.sort(key=lambda x: (-x[0], x[1]))
 
        result = []
        for person in people:
            # Insert at the position specified by k
            # Since everyone in result is >= current height,
            # inserting at index k gives exactly k taller-or-equal people in front
            result.insert(person[1], person)
 
        return result

var reconstructQueue = function(people) {
    // Sort tallest first; for equal heights, smaller k first
    people.sort((a, b) => {
        if (b[0] !== a[0]) return b[0] - a[0]; // height descending
        return a[1] - b[1];                      // k ascending for ties
    });
 
    const result = [];
    for (const person of people) {
        // Insert at position k — everyone already in result is at least as tall
        result.splice(person[1], 0, person);
    }
 
    return result;
};

Complexity Analysis:

For the standard interview, O(n^2) is acceptable since n <= 2000. The interviewer may ask about O(n log n) as a follow-up.

Common Mistakes#

• Sorting by height ascending instead of descending. If you process shorter people first, inserting them at position k does not satisfy the constraint — taller people inserted later may displace them.
• For ties in height, sorting by k descending. When two people have the same height, the one with the smaller k should be inserted first (into an earlier position). If you sort same-height people by k descending, they get inserted out of order.
• Using append instead of insert. Simply appending respects no positional constraint. The insert(k, person) call places the person at exactly position k.
• Confusing the output with a sorted array. The output is a reconstructed queue, not a sorted array. The order matters based on k values, not heights.
• Off-by-one in position. insert(k, person) inserts so that result[k] becomes the new element. This gives exactly k elements before it — matching the k constraint.

Follow-up Questions#

Q: Can this be solved in O(n log n) time? Yes, using a Binary Indexed Tree (BIT) or segment tree. The idea: process people sorted by height. For each person, find the k-th empty position using a BIT that tracks available slots. This avoids the O(n) list insertion.

Q: What if two people can have the same height AND the same k? The problem guarantees a valid unique queue, so this case does not arise in valid inputs. If it could, you would need additional tie-breaking.

Q: Why does sorting same-height people by k ascending work? Consider two people with the same height h: [h, k1] and [h, k2] where k1 < k2. We want [h, k1] to end up in an earlier position (smaller index). By inserting [h, k1] first at position k1, and then [h, k2] at position k2, the insertion at k2 will place [h, k2] after [h, k1] has already shifted some elements right — maintaining the relative ordering correctly.

Q: What if heights are not unique and k values are not unique? Still handled correctly by the sort + insert approach, as the problem guarantees a valid reconstruction exists.

Q: What does the time complexity of the JavaScript splice operation mean for large inputs? Array.splice in JavaScript has O(n) worst-case time (it shifts all elements after the insertion point). For n=2000, this gives O(n^2) = 4 million operations — acceptable. For larger n, the BIT approach would be needed.

Q: Is there a different greedy strategy that also works? Yes — process shortest people first (ascending height). For each person, count how many of their predecessors (in the output) have height >= current, and place them after exactly k such people. This is more complex to implement correctly but achieves the same result.

Related Problems#

• LeetCode 435 — Non-overlapping Intervals: Greedy with non-obvious sort key (end time) — same "right sort order unlocks greedy" pattern.
• LeetCode 452 — Minimum Arrows to Burst Balloons: Sort by end, greedy cluster formation.
• LeetCode 455 — Assign Cookies: Sort both arrays, two-pointer matching — simplest greedy with sort.
• LeetCode 1353 — Maximum Number of Events That Can Be Attended: Greedy with priority queue — attend earliest-ending available event.
• LeetCode 646 — Maximum Length of Pair Chain: Sort by second element, greedy chain selection.
• LeetCode 767 — Reorganize String: Greedy character placement — heap-based reorganisation.

Interview Tips#

• Lead with the invariant: "After inserting all taller-or-equal people, position k gives exactly k taller-or-equal people in front."
• Justify the tie-breaking rule (smaller k first) with a concrete two-element example.
• Mention the BIT/segment-tree O(n log n) optimisation as a follow-up.

Key Takeaways#

• Sort tallest-first so each insertion sees only taller-or-equal people already placed.
• For equal heights, break ties by smaller k first to keep insertion positions valid.
• insert(k, person) makes the inserted element occupy index k, giving exactly k people in front.
• The straightforward solution is O(n^2) due to list insertion; this is fine for n up to 2000.
• Use a BIT or segment tree to locate the k-th empty slot for an O(n log n) variant.
• The pattern "non-obvious sort key + simple insert" recurs in many greedy interval problems.
• Always verify the constructed queue against the original k values when testing.