{x}
blog image

Queue Reconstruction by Height

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 no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

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 <= 106
  • 0 <= ki < people.length
  • It is guaranteed that the queue can be reconstructed.

Solution Explanation:

This problem can be efficiently solved using a greedy approach combined with sorting. The core idea is to process people in decreasing order of height. For each person, we insert them into the queue at the index specified by their k value. This works because once we've placed all taller people, the k value accurately reflects the number of taller or equally tall people in front.

Algorithm:

  1. Sort: Sort the people array in descending order of height (h). If two people have the same height, sort them in ascending order of k (the number of people in front with height greater than or equal to their height). This sorting step is crucial for the greedy approach to work correctly. The reason for sorting this way is that we always consider people with the greatest height first. Once these people are sorted and placed, we don't need to worry about re-arranging them later. This ensures that k remains accurate.

  2. Insert: Iterate through the sorted people array. For each person [h, k], insert them into the ans (result) array at index k. The insert operation at index k will automatically push all subsequent elements to the right.

  3. Return: Return the ans array which now represents the reconstructed queue.

Time Complexity Analysis:

  • Sorting: The sorting step using a comparison-based sorting algorithm (like merge sort or quicksort, often used in Python's sort function and Java's Arrays.sort) has a time complexity of O(N log N), where N is the number of people.
  • Insertion: The insertion step takes O(N) in the average case for insert into a List or vector. In the worst case where many insertions happen at the beginning, it can be O(N^2). However, because of the sorting step, this worst-case scenario becomes less likely.
  • Overall: Therefore, the overall time complexity is dominated by the sorting step, resulting in O(N log N).

Space Complexity Analysis:

The space complexity is O(N) because we use an array ans to store the reconstructed queue, which has the same size as the input people array. The sorting algorithms might use additional space in some cases (e.g., merge sort uses O(N) auxiliary space), but this is still considered O(N) within the overall space complexity.

Code Examples (with comments):

The provided code examples in Python, Java, C++, and Go implement this algorithm efficiently. The key differences between the languages are primarily in the syntax for sorting and list/vector manipulation (inserting elements). The core logic remains consistent across all languages. The Go code uses sort.Slice for custom sorting. The C++ code utilizes a lambda expression for a concise sorting comparator. The Java code directly uses Arrays.sort with a custom comparator. The Python code uses a lambda expression for a compact sorting key.