Sponsored
Sponsored
In this approach, we first sort the array of people. The sorting criteria should be descending order of height and ascending order of the number of people in front for the same height. After sorting, we iterate through the list and insert each person into a new list at the index corresponding to the number of people in front of them. This ensures that each person is placed correctly with regard to the number of taller or equally tall people in front.
Time Complexity: O(n^2) due to the potential element shifting during insertion.
Space Complexity: O(1) additional space required.
1def reconstructQueue(people):
2 people.sort(key=lambda x: (-x[0], x[1]))
3 queue = []
4 for person in people:
5 queue.insert(person[1], person)
6 return queue
7
8people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
9result = reconstructQueue(people)
10
11for person in result:
12 print(person)This Python solution sorts the input list with a lambda function that defines the sorting criteria: height is sorted in descending order and the k-value in ascending order. After sorting, each person is inserted into the resulting list at the index specified by their k-value.