NUHMAN.com

📘 Problem Statement

You are given an array of people, where each person is represented by a pair (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h.

Reconstruct the queue by reconstructing it in a way that satisfies the following:

• The person at position i has height h and there are exactly k people in front of this person with a height greater than or equal to h.

Input:

• An array people where each element is a pair [h, k].

Output:

• The reconstructed queue, represented as an array of people.

🧠 Key Insight

This problem requires reconstructing a queue based on height and the number of taller or equally tall people in front. The optimal strategy is a greedy approach:

1. Sort the People: First, sort the people by their height in descending order. This ensures that we place the taller people first.
2. Insert by k Value: Then, for each person in the sorted list, insert them into the correct position in the reconstructed queue based on the value of k. This ensures that each person ends up in the correct position with k taller or equally tall people ahead of them.

💡 Approach

1. Sort the People by Height and k:

• Sort the people in descending order by height (h). If two people have the same height, sort them by k in ascending order. Sorting by k ensures that for people of the same height, those who have fewer taller people ahead are placed first.

1. Reconstruct the Queue:

• Start with an empty queue.
• For each person, insert them at the index equal to their k value. Since the taller people are placed first, this guarantees that the queue is reconstructed correctly as we go along.

🐍 Python Code

python

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # Sort people by descending height and then by ascending k value
        people.sort(key=lambda x: (-x[0], x[1]))
        
        queue = []
        for person in people:
            queue.insert(person[1], person)  # Insert at the position given by k
        return queue

🔍 Step-by-Step Explanation

1. Sorting the People:

python

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

• We sort the people by their height in descending order. If two people have the same height, we sort them by the k value in ascending order.
• Sorting by height ensures that the taller people are placed first, and sorting by k ensures that people with fewer taller people ahead are placed earlier.

2. Reconstruct the Queue:

python

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

• We initialize an empty list queue.
• For each person in the sorted list, we insert them into the queue at the index specified by their k value. Since the taller people are placed first, this guarantees that the queue is correctly reconstructed.

3. Return the Reconstructed Queue:

python

return queue

• Finally, we return the reconstructed queue as a list of people.

💡 Example Walkthrough

Example 1:

python

Input:
people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

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

• Step 1: Sort the people by height (descending) and k (ascending):
• Sorted people: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
• Step 2: Reconstruct the queue:
• Insert [7,0] at index 0: [[7,0]]
• Insert [7,1] at index 1: [[7,0], [7,1]]
• Insert [6,1] at index 1: [[7,0], [6,1], [7,1]]
• Insert [5,0] at index 0: [[5,0], [7,0], [6,1], [7,1]]
• Insert [5,2] at index 2: [[5,0], [7,0], [5,2], [6,1], [7,1]]
• Insert [4,4] at index 4: [[5,0], [7,0], [5,2], [6,1], [7,1], [4,4]]

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(n log n)Space ComplexityO(n)

• Time Complexity:
• Sorting the people list takes O(n log n), where n is the number of people. The insert operation for each person takes O(n) in the worst case, but the number of insert operations is proportional to n. Therefore, the overall time complexity is dominated by the sorting step, which is O(n log n).
• Space Complexity:
• The space complexity is O(n) because we are storing the reconstructed queue and the original list of people.

🧵 Final Thoughts

LeetCode 406 is a classic example of a queue reconstruction problem where sorting and insertion play a key role. By sorting the people first by height and then by the k value, we ensure that each person is placed in the correct position with respect to the other people ahead of them. This greedy approach ensures the correct solution with optimal time complexity. The problem tests the ability to combine sorting with insertion operations efficiently and can be generalized to other real-world applications that involve priority-based queue construction.