LeetCode 406: Queue Reconstruction by Height Solution in Python – A Step-by-Step Guide

What Is LeetCode 406: Queue Reconstruction by Height?

In LeetCode 406: Queue Reconstruction by Height, you’re given a list of pairs people, where each pair [h, k] represents a person’s height h and the number of people k in front of them who are taller (or equal height). You need to return the reconstructed queue as a list of pairs in the order they stand. For example, with [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]], you arrange them into [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]—everyone’s height and count matches their spot!

Problem Statement

• Input: A list of lists people, where people[i] = [h_i, k_i] (height, count of taller/equal ahead).
• Output: A list of lists—the queue order satisfying all conditions.
• Rules:
• k_i counts people ahead with height ≥ h_i.
• Multiple valid orders may exist; return any one.

Constraints

• 1 <= people.length <= 2000.
• 0 <= h_i <= 10⁶.
• 0 <= k_i < people.length.
• All heights are distinct or can repeat.

Examples

• 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]].
• Input: [[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]].

Understanding the Problem: Lining Up the Queue

To solve LeetCode 406: Queue Reconstruction by Height in Python, we need to arrange people so each person’s height and count of taller (or equal) people ahead matches their given pair. A naive idea might be to try every possible order—but with up to 2000 people, that’s way too many permutations! Instead, we’ll use:

• Best Solution (Greedy with Insertion): O(n²) time, O(n) space—places people strategically.
• Alternative Solution (Sorting with Adjustment): O(n²) time, O(n) space—sorts and tweaks positions.

Let’s dive into the greedy insertion solution with a clear, step-by-step explanation.

Best Solution: Greedy with Insertion

Why This Is the Best Solution

The greedy with insertion method is the top pick because it’s efficient—O(n²) time, O(n) space—and brilliantly simple once you get it. It sorts people by height (tallest first) and inserts them into the queue based on their k value, treating k as the number of empty or taller spots ahead. It’s like lining up the tallest folks first, then slotting shorter ones where they fit!

How It Works

Think of the queue as a row of chairs you’re filling:

• Step 1: Sort by Height (Tallest First):
• Sort people by height descending, then by k ascending if heights tie (e.g., [7,0], [7,1], [6,1], ...).
• Why? Tallest people’s k counts are exact since no one taller is added later.
• Step 2: Insert by k:
• Start with an empty queue.
• For each person [h, k], insert them at index k (shifting others right).
• k represents how many taller (or equal) people should be ahead, and since we add tallest first, it’s just empty spots at that point.
• Step 3: Build the Queue:
• Keep adding until everyone’s in place.
• Step 4: Why This Works:
• Tallest first ensures their k is satisfied (no taller people come later).
• Inserting at k pushes shorter people right, adjusting their counts naturally.
• It’s like placing giants first, then fitting dwarves where they belong!

Step-by-Step Example

Example: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

• Sort: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]] (height desc, k asc).
• Insert:
• [7,0]: k=0, Queue = [[7,0]].
• [7,1]: k=1, Queue = [[7,0], [7,1]] (1 taller ahead).
• [6,1]: k=1, Queue = [[7,0], [6,1], [7,1]] (insert at 1, 1 taller ahead).
• [5,0]: k=0, Queue = [[5,0], [7,0], [6,1], [7,1]] (insert at 0).
• [5,2]: k=2, Queue = [[5,0], [7,0], [5,2], [6,1], [7,1]] (insert at 2, 2 taller ahead).
• [4,4]: k=4, Queue = [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] (insert at 4).
• Result: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]].
• Verify:
• [5,0]: 0 taller ahead ✓.
• [7,0]: 0 taller ahead ✓.
• [5,2]: 2 taller (7,6) ✓.
• [6,1]: 1 taller (7) ✓.
• [4,4]: 4 taller (5,7,5,6) ✓.
• [7,1]: 1 taller (7 earlier) ✓.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # Step 1: Sort by height descending, then k ascending
        people.sort(key=lambda x: (-x[0], x[1]))

        # Step 2: Build queue by inserting at k
        queue = []
        for person in people:
            h, k = person
            queue.insert(k, person)  # Insert at index k

        return queue

• Line 4: Sort people:
• -x[0]: Height descending (tallest first).
• x[1]: k ascending if heights tie (e.g., [7,0] before [7,1]).
• Line 7-9: Build queue:
• For each [h, k]:
• queue.insert(k, person): Place at index k, shifting others right.
• E.g., [6,1] into [[7,0], [7,1]] → [[7,0], [6,1], [7,1]].
• Line 11: Return the final queue.
• Time Complexity: O(n²)—sorting O(n log n), n insertions O(n) each.
• Space Complexity: O(n)—queue storage.

This is like slotting people into a lineup with a height-first rule!

Alternative Solution: Sorting with Adjustment

Why an Alternative Approach?

The sorting with adjustment method sorts by k first, then adjusts positions to satisfy height conditions. It’s O(n²) time and O(n) space—less intuitive but a different take. It’s like guessing a line based on k, then shuffling to fit heights!

How It Works

Picture it as a draft lineup:

• Step 1: Sort by k ascending, height descending.
• Step 2: Place each person, shifting if needed to match k.
• Step 3: Adjust until all conditions hold.

Step-by-Step Example

Example: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

• Sort by k, then h desc: [[5,0], [7,0], [6,1], [7,1], [5,2], [4,4]].
• Place:
• [5,0]: [[5,0]].
• [7,0]: [[7,0], [5,0]] (adjust for k=0).
• [6,1]: [[7,0], [6,1], [5,0]].
• [7,1]: [[7,0], [7,1], [6,1], [5,0]].
• [5,2]: [[7,0], [7,1], [5,2], [6,1], [5,0]].
• [4,4]: [[7,0], [7,1], [5,2], [6,1], [4,4], [5,0]].
• Result: Matches best solution after tweaks.

Code for Sorting Adjustment Approach

Copy codeclass Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # Sort by k ascending, height descending
        people.sort(key=lambda x: (x[1], -x[0]))

        queue = []
        for h, k in people:
            # Count taller ahead, adjust position
            pos = 0
            taller = 0
            while pos < len(queue) and taller < k:
                if queue[pos][0] >= h:
                    taller += 1
                pos += 1
            queue.insert(pos, [h, k])

        return queue

• Time Complexity: O(n²)—n insertions with checks.
• Space Complexity: O(n)—queue.

It’s a k-first shuffle!

Comparing the Two Solutions

• Greedy with Insertion (Best):
• Pros: O(n²), O(n), clear and efficient.
• Cons: Insertion cost.
• Sorting with Adjustment (Alternative):
• Pros: O(n²), O(n), alternative logic.
• Cons: More complex adjustments.

Greedy wins for clarity.

Additional Examples and Edge Cases

• [[5,0]]: [[5,0]].
• [[7,0],[7,1]]: [[7,0],[7,1]].
• []: [] (empty ok per problem).

Greedy handles all.

Complexity Breakdown

• Greedy with Insertion: Time O(n²), Space O(n).
• Sorting with Adjustment: Time O(n²), Space O(n).

Greedy’s sleek.

Key Takeaways

• Greedy Insertion: Tallest first!
• Sorting Adjustment: k-first tweak!
• Queues: Positioning is key.
• Python Tip: Sorting rocks—see [Python Basics](/python/basics).

Final Thoughts: Line ‘Em Up

LeetCode 406: Queue Reconstruction by Height in Python is a lineup challenge. Greedy insertion nails it fast, while sorting adjusts it out. Want more sorting fun? Try LeetCode 75: Sort Colors or LeetCode 215: Kth Largest Element. Ready to queue? Head to Solve LeetCode 406 on LeetCode and reconstruct that line today!