Problem Description

You have an array called people where each element represents a person in a queue. Each person is described by two values: [height, k], where:

• height is the person's height
• k is the number of people in front of this person who have a height greater than or equal to their height

The array people is scrambled and not in the correct queue order. Your task is to reconstruct the proper queue arrangement.

For example, if a person has attributes [7, 2], this means:

• The person has height 7
• There should be exactly 2 people in front of them with height ≥ 7

The solution works by:

1. Sorting people by height in descending order (tallest first). If heights are equal, sort by k value in ascending order
2. Building the queue by inserting each person at position k in the result array

The key insight is that when we process people from tallest to shortest, we can directly insert each person at index k because:

• All taller people are already placed in the queue
• The current person's k value tells us exactly where they should go among the taller people
• Shorter people added later won't affect the k count for taller people already placed

For instance, with input [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]:

• After sorting: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
• Insert [7,0] at position 0: [[7,0]]
• Insert [7,1] at position 1: [[7,0],[7,1]]
• Insert [6,1] at position 1: [[7,0],[6,1],[7,1]]
• Continue this process to get final result: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Intuition

The key observation is that taller people don't care about shorter people in front of them when counting how many people are taller or equal to them. This suggests we should handle people by height.

If we process people from tallest to shortest, we gain a powerful advantage: when placing a person, all people who could affect their k count (people of equal or greater height) have already been placed. This means the k value directly tells us the insertion position.

Think about it this way: if you're the tallest person with k=0, you must go to the front. If another equally tall person has k=1, they go right after you. When we move to shorter people, they can squeeze in between taller people without affecting the taller people's counts.

For example, if we have already placed people of height 7 and 6, and now we need to place someone of height 5 with k=2, we know exactly that this person needs to be at index 2 among the current queue. The beauty is that this person of height 5 won't disturb the k values of the taller people already placed - they don't count people shorter than themselves.

This greedy approach works because:

1. By sorting in descending height order, we ensure all people who matter for the current person's position are already placed
2. By using the secondary sort on k (ascending), we handle people of the same height correctly - those with smaller k values go first
3. The insert operation at index k naturally pushes existing elements to the right, maintaining the relative order we've built so far

The algorithm essentially builds the queue layer by layer, from tallest to shortest, with each person finding their exact spot based on how many taller/equal people should be in front of them.

Solution Approach

The implementation uses a greedy algorithm with custom sorting and dynamic insertion:

Step 1: Sort the people array

people.sort(key=lambda x: (-x[0], x[1]))

This sorts people by:

• Primary key: height in descending order (using -x[0] to reverse the order)
• Secondary key: k value in ascending order (using x[1])

For example, [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] becomes [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

Step 2: Build the result queue

ans = []
for p in people:
    ans.insert(p[1], p)

We iterate through the sorted array and insert each person at index p[1] (which is their k value).

Let's trace through the example:

• Start with empty ans = []
• Insert [7,0] at index 0: ans = [[7,0]]
• Insert [7,1] at index 1: ans = [[7,0],[7,1]]
• Insert [6,1] at index 1: ans = [[7,0],[6,1],[7,1]] (pushes [7,1] to the right)
• Insert [5,0] at index 0: ans = [[5,0],[7,0],[6,1],[7,1]]
• Insert [5,2] at index 2: ans = [[5,0],[7,0],[5,2],[6,1],[7,1]]
• Insert [4,4] at index 4: ans = [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Time Complexity: O(n^2) where n is the number of people

• Sorting takes O(n log n)
• Each insertion can take O(n) in the worst case (when inserting at the beginning)
• Total: O(n log n) + O(n^2) = O(n^2)

Space Complexity: O(n) for the result array

The pattern used here is a greedy approach where we make locally optimal choices (placing each person at their exact k position) that lead to a globally optimal solution. The key insight is that processing from tallest to shortest ensures that each insertion decision is made with complete information about all relevant (taller or equal height) people.

Example Walkthrough

Let's work through a small example with people = [[5,0],[6,0],[5,2],[7,0]].

Step 1: Sort by height (descending) and k (ascending)

• Original: [[5,0],[6,0],[5,2],[7,0]]
• After sorting: [[7,0],[6,0],[5,0],[5,2]]
  • 7 comes first (tallest)
  • 6 comes next
  • Both 5s have same height, so we sort by k: [5,0] before [5,2]

Step 2: Build the queue by inserting at index k

Starting with empty result: []

1. Insert [7,0] at index 0:

   • Result: [[7,0]]
   • Person with height 7 wants 0 people ≥7 in front → goes to position 0

2. Insert [6,0] at index 0:

   • Result: [[6,0],[7,0]]
   • Person with height 6 wants 0 people ≥6 in front → goes to position 0
   • This pushes [7,0] to position 1
   • Note: [6,0] doesn't affect [7,0]'s count since 6 < 7

3. Insert [5,0] at index 0:

   • Result: [[5,0],[6,0],[7,0]]
   • Person with height 5 wants 0 people ≥5 in front → goes to position 0
   • Pushes everyone else to the right

4. Insert [5,2] at index 2:

   • Result: [[5,0],[6,0],[5,2],[7,0]]
   • Person with height 5 wants 2 people ≥5 in front
   • At index 2, they have [5,0] and [6,0] in front (both ≥5) ✓

Final verification:

• [5,0]: 0 people ≥5 in front ✓
• [6,0]: 0 people ≥6 in front ✓
• [5,2]: 2 people ≥5 in front ([5,0] and [6,0]) ✓
• [7,0]: 0 people ≥7 in front ✓

The key insight: when we insert shorter people, they don't invalidate the k-counts of taller people already placed, since taller people only count those who are as tall or taller than themselves.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2) where n is the number of people.

• The sorting operation takes O(n log n) time.
• The insertion loop runs n times, and each insert() operation at position p[1] takes O(n) time in the worst case (when inserting at the beginning of the list, all subsequent elements need to be shifted).
• Therefore, the overall time complexity is O(n log n) + O(n^2) = O(n^2).

Space Complexity: O(n) where n is the number of people.

• The ans list stores all n people, requiring O(n) space.
• The sorting operation in Python uses Timsort, which requires O(n) auxiliary space in the worst case.
• No other significant auxiliary space is used.
• Therefore, the total space complexity is O(n).

Common Pitfalls

1. Incorrect Sorting Logic

A common mistake is getting the sorting criteria wrong, which breaks the entire algorithm.

Pitfall Example:

# Wrong: Sorting both in ascending order
people.sort(key=lambda x: (x[0], x[1]))

# Wrong: Sorting height ascending, k descending
people.sort(key=lambda x: (x[0], -x[1]))

Why it fails: If we process shorter people first, we don't know where taller people will be placed later, making it impossible to determine the correct position based on the k value.

Solution: Always sort by height descending first, then by k ascending:

people.sort(key=lambda x: (-x[0], x[1]))

2. Using Index Assignment Instead of Insert

Another mistake is trying to directly assign to an index position rather than using insert.

Pitfall Example:

result = [None] * len(people)  # Pre-allocate array
for person in people:
    result[person[1]] = person  # Wrong: direct assignment

Why it fails: Direct assignment doesn't shift existing elements. When processing [6,1] after placing [7,0] and [7,1], we'd overwrite [7,1] instead of inserting between them.

Solution: Use the insert() method which shifts elements to the right:

result = []
for person in people:
    result.insert(person[1], person)

3. Not Handling Edge Cases

Failing to consider special input scenarios can cause errors.

Pitfall Example:

def reconstructQueue(self, people):
    if not people:  # Forgetting this check
        return []
    people.sort(key=lambda x: (-x[0], x[1]))
    # ... rest of code

Common edge cases to consider:

• Empty array: []
• Single person: [[5,0]]
• All people same height: [[5,0], [5,1], [5,2]]
• All k values are 0: [[7,0], [6,0], [5,0]]

Solution: The base algorithm actually handles these cases naturally, but it's good practice to verify:

def reconstructQueue(self, people):
    # Empty array naturally returns empty result
    people.sort(key=lambda x: (-x[0], x[1]))
    result = []
    for person in people:
        result.insert(person[1], person)
    return result

4. Misunderstanding the k Value

Some might think k represents people strictly taller (not equal height).

Pitfall Understanding: Assuming [7,1] means "1 person strictly taller than 7" rather than "1 person with height ≥ 7".

Solution: Remember that k counts people with height greater than or equal to the current person's height. This is why when we have multiple people with the same height, we sort them by k value in ascending order - so that among people of the same height, those who should come first (smaller k) are processed first.