291. Queue Reconstruction by Height
🔗 LeetCode Problem: 406. Queue Reconstruction by Height
📊 Difficulty: Medium
🏷️ Topics: Array, Greedy, Sorting
Problem Statement
You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.
Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).
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 0 has height 5 with 0 people taller or the same height in front.
Person 1 has height 7 with 0 people taller or the same height in front.
Person 2 has height 5 with 2 people taller or the same height in front.
Person 3 has height 6 with 1 person taller or the same height in front.
Person 4 has height 4 with 4 people taller or the same height in front.
Person 5 has height 7 with 1 person taller or the same height in front.
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]]
Constraints:
- 1 <= people.length <= 2000
- 0 <= hi <= 10^6
- 0 <= ki < people.length
- It is guaranteed that the queue can be reconstructed.
🌳 Visual Understanding - The Queue Problem
The Problem We're Solving:
Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
h k h k h k h k h k h k
Where:
h = height of person
k = number of people IN FRONT who are >= this height
Goal: Arrange these people in a queue (order) such that
each person has EXACTLY k people in front who are >= their height
Understanding the Notation:
Person [7, 0]:
- Height = 7
- k = 0 → "0 people in front who are >= 7"
- This person should be at a position where NO ONE taller/equal is in front
Person [4, 4]:
- Height = 4
- k = 4 → "4 people in front who are >= 4"
- This person should be at a position where EXACTLY 4 people >= 4 are in front
Person [7, 1]:
- Height = 7
- k = 1 → "1 person in front who is >= 7"
- This person should be at a position where EXACTLY 1 person >= 7 is in front
What Does "In Front" Mean?
Queue (left to right):
Position: 0 1 2 3 4 5
[__][__][__][__][__][__]
↑
Front of queue
If person X is at position 3:
"In front of X" = positions 0, 1, 2
Example:
Queue: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
For person at position 4 ([4,4]):
People in front: [[5,0], [7,0], [5,2], [6,1]]
How many are >= 4? ALL of them! (5, 7, 5, 6 all >= 4)
Count = 4 ✓ Matches k=4!
Key Observations:
1. Each person is [height, k]
- height: their actual height
- k: count constraint (people >= height in front)
2. We need to RECONSTRUCT the queue
- Input is UNORDERED
- Output must satisfy all k constraints
3. Multiple people can have same height
- [7,0] and [7,1] both have height 7
- But different k values
4. Solution is UNIQUE
- Only ONE correct arrangement exists
🧠 The AHA Moment - Why This Order Works
The Brute Force Nightmare:
Try all possible arrangements:
- n! permutations for n people
- For each permutation, verify all k constraints
- This is O(n! × n) - IMPOSSIBLE! 😰
Example: 6 people → 6! = 720 arrangements to check!
The Key Insight - Greedy with Tall People First
Discovery: What if we process tall people first?
Think about it:
If we place TALL people first:
- They don't care about shorter people behind them!
- Shorter people DON'T COUNT for tall people's k value!
Example:
Person [7, 0]: height 7, k=0
If we place them first, we only count people >= 7 in front
Any shorter people (like height 4, 5, 6) DON'T affect them!
This is the KEY insight! 🔑
Visual Discovery - Why Tall First Works
Let's process people by height (tallest first):
People: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Sort by height (descending):
[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
↓ ↓ ↓ ↓ ↓ ↓
H=7 H=7 H=6 H=5 H=5 H=4
Now process one by one:
Step 1: Place [7,0]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k=0 → "0 people >= 7 in front"
Insert at position 0 (beginning)
Queue: [[7,0]]
Step 2: Place [7,1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k=1 → "1 person >= 7 in front"
Currently in queue: [7,0] (only 1 person >= 7)
Insert at position 1 (after [7,0])
Queue: [[7,0], [7,1]]
Step 3: Place [6,1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k=1 → "1 person >= 6 in front"
Currently in queue: [7,0], [7,1] (both are >= 6)
KEY OBSERVATION:
For height 6, people with height 7 COUNT!
We need 1 person >= 6 in front
Insert at position 1 (between [7,0] and [7,1])
Queue: [[7,0], [6,1], [7,1]]
Step 4: Place [5,0]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k=0 → "0 people >= 5 in front"
Insert at position 0 (beginning)
Queue: [[5,0], [7,0], [6,1], [7,1]]
Step 5: Place [5,2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k=2 → "2 people >= 5 in front"
Currently: [5,0], [7,0], [6,1], [7,1]
People >= 5: [5,0], [7,0], [6,1], [7,1] - all of them!
Need 2 in front → insert at position 2
Queue: [[5,0], [7,0], [5,2], [6,1], [7,1]]
Step 6: Place [4,4]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
k=4 → "4 people >= 4 in front"
Currently: [5,0], [7,0], [5,2], [6,1], [7,1]
People >= 4: ALL of them! (5,7,5,6,7 all >= 4)
Need 4 in front → insert at position 4
Queue: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
FINAL ANSWER! ✓
Why This Greedy Approach Works
The Magic Property:
When we process tall people first:
1. We place them according to their k values
2. When we place shorter people later:
- We INSERT them at position k
- This DOESN'T affect taller people's k counts!
- Because shorter people don't count for taller people!
Example:
Placed [7,0] at position 0
Later insert [5,0] at position 0
[7,0] moves to position 1
But [5,0] doesn't count for [7,0]'s k value (5 < 7)
So [7,0] still has 0 people >= 7 in front ✓
This is why greedy works:
- Taller people set up positions
- Shorter people "squeeze in" without breaking constraints! 🎯
The Sorting Strategy
Sort by TWO criteria:
1. Height (descending): Process tall people first
[7, X], [7, Y], [6, Z], [5, A], [5, B], [4, C]
2. Within same height, k (ascending): Process smaller k first
[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]
↑ ↑
Same height → sort by k
Why sort by k within same height?
If both have height 7:
[7,0] should come before [7,1]
Because [7,0] needs 0 people >= 7 in front
And [7,1] needs 1 person >= 7 in front
Processing [7,0] first makes sense!
🔴 Approach 1: Brute Force (Too Slow - For Understanding Only)
💡 Intuition
"Try all possible arrangements and check each one"
For each permutation of people:
Check if all k constraints are satisfied
If yes, return this arrangement
This helps understand the problem but is TOO SLOW!
📝 Implementation (Conceptual)
// This is TOO SLOW for actual use!
// Just for understanding the problem
class Solution {
public int[][] reconstructQueue(int[][] people) {
// Generate all permutations
List<int[][]> allPermutations = generatePermutations(people);
// Check each permutation
for (int[][] arrangement : allPermutations) {
if (isValid(arrangement)) {
return arrangement;
}
}
return people; // Should never reach here
}
private boolean isValid(int[][] arrangement) {
// Check if each person's k constraint is satisfied
for (int i = 0; i < arrangement.length; i++) {
int height = arrangement[i][0];
int expectedK = arrangement[i][1];
// Count people in front who are >= this height
int actualK = 0;
for (int j = 0; j < i; j++) {
if (arrangement[j][0] >= height) {
actualK++;
}
}
// If constraint not satisfied, this arrangement is wrong
if (actualK != expectedK) {
return false;
}
}
return true; // All constraints satisfied!
}
}
📊 Complexity Analysis
Time Complexity: O(n! × n)
Generate all permutations: O(n!)
Check each permutation: O(n)
Total: O(n! × n)
For n=6: 6! × 6 = 4,320 operations
For n=10: 10! × 10 = 36,288,000 operations!
WAY TOO SLOW! ⚠️
🟢 Approach 2: Greedy with Sorting (Optimal)
🎨 Building Deep Intuition - Step by Step
Let me show you WHY this greedy approach works with detailed reasoning:
Step 1: Why Process Tall People First?
Key Insight: Shorter people are "invisible" to taller people!
Example:
Person A: [7, 0] - height 7, needs 0 people >= 7 in front
Person B: [5, 0] - height 5, needs 0 people >= 5 in front
Scenario 1: Place [7,0] first, then insert [5,0]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: Place [7,0]
Queue: [[7,0]]
Step 2: Insert [5,0] at position 0
Queue: [[5,0], [7,0]]
Check [7,0]:
People in front >= 7: none (5 < 7, doesn't count!)
Expected k = 0 ✓ CORRECT!
Check [5,0]:
People in front >= 5: none
Expected k = 0 ✓ CORRECT!
Scenario 2: Place [5,0] first, then [7,0]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: Place [5,0]
Queue: [[5,0]]
Step 2: Where to place [7,0]?
[7,0] needs 0 people >= 7 in front
But we have [5,0] in queue
If we put [7,0] anywhere, position matters for [5,0]!
[5,0] would see [7,0] and its k would change!
This is MESSY! Hard to manage! ✗
CONCLUSION:
Tall first is EASIER because:
- Tall people set their positions
- Short people insert without affecting tall people
- Clean and simple! ✓
Step 2: Why Insert at Position k?
When we process person [h, k]:
- k tells us "how many people >= h should be in front"
- All people already in queue are >= h (we sorted tall first!)
- So we need EXACTLY k of them in front
- Therefore: Insert at position k!
Example:
Queue: [[7,0], [7,1], [7,2]]
Now insert [6, 1]:
- height 6, k=1
- People in queue: all height 7 (all >= 6)
- Need 1 person >= 6 in front
- Insert at position 1!
Result: [[7,0], [6,1], [7,1], [7,2]]
Verification:
[6,1] has [[7,0]] in front → 1 person >= 6 ✓
Step 3: Detailed Example - Why It All Works
People: [[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]]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [7,0]: height=7, k=0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Insert at position k=0
Queue: [[7,0]]
↑ position 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [7,1]: height=7, k=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Insert at position k=1
Queue: [[7,0], [7,1]]
↑ pos 0 ↑ pos 1
Reasoning:
[7,1] needs 1 person >= 7 in front
Currently have [7,0] (which is >= 7)
Position 1 puts [7,0] in front ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [6,1]: height=6, k=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Insert at position k=1
Queue: [[7,0], [6,1], [7,1]]
↑ pos 0 ↑ pos 1 ↑ pos 2
Reasoning:
[6,1] needs 1 person >= 6 in front
Currently: [7,0], [7,1] (both are >= 6)
Position 1 puts EXACTLY 1 person ([7,0]) in front ✓
Key Observation:
[7,1] was at position 1, now moved to position 2
But [6,1] doesn't affect [7,1]'s k!
[7,1] still has 1 person >= 7 in front ([7,0]) ✓
Because 6 < 7, so [6,1] doesn't count for [7,1]!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [5,0]: height=5, k=0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Insert at position k=0
Queue: [[5,0], [7,0], [6,1], [7,1]]
Reasoning:
[5,0] needs 0 people >= 5 in front
Position 0 (beginning) achieves this ✓
Effect on others:
[7,0] moved from pos 0 to pos 1
Still has 0 people >= 7 in front (5 < 7 doesn't count) ✓
[6,1] moved from pos 1 to pos 2
Has [5,0] and [7,0] in front, but only [7,0] counts (7 >= 6)
Still 1 person >= 6 in front ✓
[7,1] moved from pos 2 to pos 3
Has [5,0] and [7,0] in front, but only [7,0] counts
Still 1 person >= 7 in front ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [5,2]: height=5, k=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Insert at position k=2
Queue: [[5,0], [7,0], [5,2], [6,1], [7,1]]
Reasoning:
[5,2] needs 2 people >= 5 in front
Currently: [5,0], [7,0], [6,1], [7,1] (all >= 5)
Position 2 puts EXACTLY 2 people in front ([5,0], [7,0]) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [4,4]: height=4, k=4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Insert at position k=4
Queue: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
Reasoning:
[4,4] needs 4 people >= 4 in front
Currently: [5,0], [7,0], [5,2], [6,1], [7,1] (all >= 4!)
Position 4 puts EXACTLY 4 people in front ✓
FINAL ANSWER: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] ✓
📝 Implementation - Clean and Simple
import java.util.*;
class Solution {
public int[][] reconstructQueue(int[][] people) {
// Step 1: Sort people
// - By height (descending): tall people first
// - By k (ascending): smaller k first for same height
Arrays.sort(people, (a, b) -> {
if (a[0] != b[0]) {
return b[0] - a[0]; // Height descending
} else {
return a[1] - b[1]; // k ascending
}
});
// Step 2: Insert people one by one at position k
List<int[]> result = new ArrayList<>();
for (int[] person : people) {
int k = person[1];
result.add(k, person); // Insert at position k
}
// Convert to array and return
return result.toArray(new int[people.length][2]);
}
}
🔍 Complete Dry Run
Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Sort
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
After sorting:
[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Insert one by one
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Insert [7,0] at position 0:
result = [[7,0]]
Insert [7,1] at position 1:
result = [[7,0], [7,1]]
Insert [6,1] at position 1:
result = [[7,0], [6,1], [7,1]]
Insert [5,0] at position 0:
result = [[5,0], [7,0], [6,1], [7,1]]
Insert [5,2] at position 2:
result = [[5,0], [7,0], [5,2], [6,1], [7,1]]
Insert [4,4] at position 4:
result = [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
VERIFICATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[5,0] at pos 0: 0 people >= 5 in front ✓
[7,0] at pos 1: 0 people >= 7 in front (5 doesn't count) ✓
[5,2] at pos 2: 2 people >= 5 in front ([5,0],[7,0]) ✓
[6,1] at pos 3: 1 person >= 6 in front ([7,0]) ✓
[4,4] at pos 4: 4 people >= 4 in front (all) ✓
[7,1] at pos 5: 1 person >= 7 in front ([7,0]) ✓
All constraints satisfied! ✓
📊 Complexity Analysis
Time Complexity: O(n²)
Sorting: O(n log n)
Inserting n people: O(n²)
- Each insert can be O(n) for ArrayList
- n insertions → O(n²)
Total: O(n log n) + O(n²) = O(n²)
Space Complexity: O(n)
Result list: O(n)
Note: Can be optimized to O(n log n) using more complex data structures (like balanced BST), but O(n²) is acceptable for this problem given constraints.
💡 Key Insights Summary
The Three Critical Points:
1. Process Tall People First
Why? Shorter people don't affect taller people's k values!
Tall person [7,0]:
Only cares about people >= 7
People with height 6, 5, 4 are "invisible" to them!
This makes the problem simpler! ✓
2. Insert at Position k
Why? k tells exactly how many should be in front!
Person [h, k]:
- All people in queue so far are >= h (sorted tall first)
- Need k of them in front
- Insert at position k achieves this! ✓
3. Order Within Same Height Matters
For people with same height, process smaller k first!
Why? [7,0] should come before [7,1]
[7,0] needs 0 people >= 7 in front
[7,1] needs 1 person >= 7 in front
If we place [7,0] first, it naturally satisfies both! ✓
🎯 Pattern Recognition
Template for Height-Based Problems
// Pattern: Sort + Greedy Insertion
class Solution {
public TYPE solve(TYPE[][] input) {
// Step 1: Sort with strategy
Arrays.sort(input, (a, b) -> {
// Primary: One dimension (often descending)
if (a[0] != b[0]) return b[0] - a[0];
// Secondary: Other dimension (often ascending)
return a[1] - b[1];
});
// Step 2: Greedy insertion
List<TYPE[]> result = new ArrayList<>();
for (TYPE[] item : input) {
result.add(item[POSITION], item);
}
return result.toArray(...);
}
}
Related Problems
- Russian Doll Envelopes (LC 354)
Similar sorting strategy
- Maximum Height by Stacking Cuboids (LC 1691)
Multi-dimensional sorting
- Merge Intervals (LC 56)
Sorting + greedy merging
⚠️ Common Mistakes
// Mistake 1: Wrong sort order
Arrays.sort(people, (a, b) -> a[0] - b[0]); // ❌ Ascending!
// ✓ CORRECT: Descending
Arrays.sort(people, (a, b) -> b[0] - a[0]);
// Mistake 2: Not sorting by k within same height
Arrays.sort(people, (a, b) -> b[0] - a[0]); // ❌ Missing k sort!
// ✓ CORRECT:
Arrays.sort(people, (a, b) -> {
if (a[0] != b[0]) return b[0] - a[0];
return a[1] - b[1]; // k ascending!
});
// Mistake 3: Inserting at wrong position
result.add(person); // ❌ Adds at end!
// ✓ CORRECT:
result.add(person[1], person); // Insert at position k!
// Mistake 4: Not using List for insertion
int[][] result = new int[n][2];
// Inserting in middle of array is expensive!
// ✓ CORRECT: Use ArrayList for O(n) insertion
List<int[]> result = new ArrayList<>();
📝 Quick Revision Notes
🎯 Core Concept
Problem: Reconstruct queue where each person [h,k] has exactly k people >= h in front
Key Insight: Process tall people first! Shorter people don't affect tall people's constraints.
Algorithm: 1. Sort: Height descending, k ascending 2. Insert each person at position k
Why It Works: - Tall first → short people "invisible" to them - Insert at k → exactly k people in front - Maintains all constraints! ✓
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int[][] reconstructQueue(int[][] people) {
// Example
// Input:
// [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
// This means:
// [7,0] → A person of height 7 has 0 taller or equal people in front.
// [4,4] → A person of height 4 has 4 taller or equal people in front.
// [7,1] → A person of height 7 has 1 taller or equal person in front.
// And so on...
// Output:
// A correctly arranged queue where each person’s conditions are met.
// Correct Output:
// [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
// Let's break it down step by step to see why this output is correct.
// 1st [5,0] Person of height 5 has 0 taller or equal people in front. ✅
// 2nd [7,0] Person of height 7 has 0 taller or equal people in front. ✅
// 3rd [5,2] Person of height 5 has 2 taller or equal people in front (7 and 5).
// ✅
// 4th [6,1] Person of height 6 has 1 taller or equal person in front (7). ✅
// 5th [4,4] Person of height 4 has 4 taller or equal people in front (5, 7, 5,
// 6). ✅
// 6th [7,1] Person of height 7 has 1 taller or equal person in front (7). ✅
// Why Is This Correct?
// Each person’s k condition is satisfied.
// Every person has exactly k taller/equal people in front of them.
return greedy(people);
}
private int[][] greedy(int[][] a) {
// Approach: no logic, only observation
// step 1: sort by height (descending) and k (ascending)
// initial: { 7, 0 }, { 4, 4 }, { 7, 1 }, { 5, 0 }, { 6, 1 }, { 5, 2 }
// sorted: {7, 0}, {7, 1}, {6, 1}, {5, 0}, {5, 2}, {4, 4}
Arrays.sort(a, (p1, p2) -> {
if (p1[0] != p2[0]) {
return p2[0] - p1[0];
} else {
return p1[1] - p2[1];
}
});
// step 2: process each record and put in correct position
List<int[]> reordered = new ArrayList<>();
for (int[] person : a) {
reordered.add(person[1], person);
}
// step 3: covert to required format which is array
// [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
return reordered.toArray(new int[a.length][2]);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(Arrays
.deepToString(s.reconstructQueue(new int[][] { { 7, 0 }, { 4, 4 }, { 7, 1 }, { 5, 0 }, { 6, 1 }, { 5, 2 } })));
}
}
🔑 Key Points
✓ Sort: Height DESC, k ASC
✓ Tall first: Shorter people don't affect them
✓ Insert at position k: Exactly k people in front
✓ Time: O(n²), Space: O(n)
✓ Greedy works because of "invisibility" property
🎪 Memory Aid
"Tall people first, they don't care about shorties!"
"Insert at position k, that's where they fit!"
"Sort desc height, asc k within!"
"Greedy placement, constraints maintain!" ✨
🎉 Congratulations!
You've mastered Queue Reconstruction by Height!
What You Learned:
✅ Greedy + Sorting - Powerful combination
✅ Two-dimensional sorting - Height then k
✅ Insertion strategy - Position k is key
✅ Invisibility property - Shorter don't affect taller
✅ Why greedy works - Deep understanding
The Beautiful Insight:
Complex Constraint Problem → Simple Greedy Solution
The magic insight:
Shorter people are "invisible" to taller people!
This means:
- Process tall first
- They set their positions
- Short "squeeze in" without breaking constraints
One clever observation → Elegant solution! 🎯
This is the power of Greedy:
Find the right order to process items
Each step maintains all constraints
Global solution emerges naturally! ✨
Interview Mastery:
When asked about Queue Reconstruction:
1. Understand: "[h,k] means k people >= h in front"
2. Key insight: "Process tall first!
Shorter people don't affect tall people's k values"
3. Sorting strategy: "Height descending, k ascending"
4. Algorithm: "Insert each person at position k
This gives exactly k people in front"
5. Why it works: "Tall people set positions,
short people insert without breaking constraints"
6. Code it: Clean O(n²) solution
Shows complete understanding! 💯
You've mastered an elegant greedy algorithm with sorting! 🚀✨🎯