algoadvance

You are given an array of people, people, which represents the attributes of n people in a queue (not necessarily in the correct order). Each people[i] = [hi, ki] represents the ith person of height hi with ki people in front of them who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The queue is returned in the format of an array of the same length as people where the jth person in the queue is denoted as queue[j] = [hj, kj].

Example

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]]

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]]

Clarifying Questions

  1. Q: Can there be multiple people with the same height and k value? A: Yes, it is possible for multiple people to have the same height and k value.

  2. Q: Can the array contain people with non-positive heights or negative values for k? A: No, according to the problem constraints, heights are positive integers and k is a non-negative integer.

  3. Q: Is the input guaranteed to be valid and formable into a queue? A: Yes, the input is always valid and can be reconstructed into a queue.

Strategy

  1. Sort the people array:
    • First by height in descending order.
    • Within the same height, by k value in ascending order.
  2. Insert each person into the queue:
    • Initialize an empty list to represent the queue.
    • Iterate over the sorted list and insert each person into the k index of the current queue. This places the current person at the position such that there are exactly k people in front of themselves who are at least as tall.

By sorting in this specified manner, we ensure that when we insert each person by their k value, the remaining list is always valid and maintains the required order.

Code

def reconstructQueue(people):
    # Sort the people: first by height in descending order, 
    # and by number of people in front (k) in ascending order for those with the same height.
    people.sort(key=lambda x: (-x[0], x[1]))
    
    queue = []
    # Insert each person into the queue based on the k value
    for person in people:
        queue.insert(person[1], person)
        
    return queue

# Example usage:
people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
print(reconstructQueue(people))  # Output: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

Time Complexity

Therefore, the overall time complexity of this solution is (O(n^2)).

If you have any further questions or need additional clarifications, feel free to ask!

Try our interview co-pilot at AlgoAdvance.com