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.
1function reconstructQueue(people) {
2 people.sort((a, b) => {
3 return a[0] === b[0] ? a[1] - b[1] : b[0] - a[0];
4 });
5
6 const queue = [];
7 for (let person of people) {
8 queue.splice(person[1], 0, person);
9 }
10 return queue;
11}
12
13const people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]];
14const result = reconstructQueue(people);
15console.log(result);In this JavaScript solution, the built-in sort function is utilized with a custom sorting function that sorts by height in descending order and by the k-value in ascending order. The splice function is used to insert each person into the queue at the correct position according to their k-value.