The O(n) Club: Queue Reconstruction by Height is Just Tall-Tale Sorting

The O(n) Club: Queue Reconstruction by Height is Just Tall-Tale Sorting

⚡ TL;DR

You get a list of [height, k] for people—k means “number of people as tall or taller in front.”
Don’t try brute force unless you’re paid by the CPU cycle. Just sort by height descending, then by k ascending, and insert into a list at index k.

Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
List<int> result = new LinkedList<>();
for (int[] p : people) result.add(p[1], p);</int>

🧠 How Devs Usually Mess This Up

Ah, the classic ways to go astray: Actually simulating every insert and recalculating k for everyone—no need to trigger a performance panic attack! Or thinking k is an absolute position: it isn’t. Or assuming there’s only one right answer, when in fact any lineup that fits the rules is legal. (Yes, even if it looks weird—just like company all-hands photos.)

🔍 What’s Actually Going On

This problem is “let the divas sort themselves out” as an algorithm. The biggest egos—er, tallest folks—don’t care about the shorties behind them. If you seat all tall people first, their k is fully respected. When you pop shorter people in, they fit perfectly around the already-seated giants, yanking nobody’s contract. It’s event planning 101: satisfy the neediest VIPs first, then fill the gaps with interns. That’s what greedy means here: give the least flexible constraints top billing!

🛠️ PseudoCode

• Sort people by height descending, then k ascending:

  Arrays.sort(people, (a, b) ->
    a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);

• Make an empty list queue
• For each person in people:
  • Insert them at position k in queue
• Return queue as a 2D array

💻 The Code

import java.util.*;
 public class QueueByHeight {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] != b[0]) return b[0] - a[0];
            return a[1] - b[1];
        });
        List<int> queue = new LinkedList<>();
        for (int[] p : people) {
            queue.add(p[1], p);
        }
        return queue.toArray(new int[people.length][2]);
    }
}</int>

⚠️ Pitfalls, Traps & Runtime Smacks

• Inserting into the middle of a LinkedList isn’t as fast as Java makes it look: O(n) per insert, so up to O(n²). For LeetCode limits, who cares?
• k counts “how many as tall or taller in front,” not absolute position. Off-by-one bugs are a rite of passage.
• Multiple valid outputs! Don’t panic if yours doesn’t match the examples verbatim.
• If k=0: up front, instant VIP status.

🧠 Interviewer Brain-Tattoo

“Sort first, ask questions later. If greedy works and your code’s still readable, you probably nailed the interview.”