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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[][] ReconstructQueue(int[][] people) {
6 Array.Sort(people, (a, b) => {
7 if (a[0] != b[0]) return b[0] - a[0];
8 return a[1] - b[1];
9 });
10
11 List<int[]> queue = new List<int[]>();
12 foreach (var person in people) {
13 queue.Insert(person[1], person);
14 }
15
16 return queue.ToArray();
17 }
18
19 public static void Main() {
20 Solution sol = new Solution();
21 int[][] people = new int[][] {
22 new int[] { 7, 0 }, new int[] { 4, 4 }, new int[] { 7, 1 },
23 new int[] { 5, 0 }, new int[] { 6, 1 }, new int[] { 5, 2 }
24 };
25
26 int[][] result = sol.ReconstructQueue(people);
27
28 foreach (var person in result) {
29 Console.Write("[" + string.Join(", ", person) + "] ");
30 }
31 }
32}This C# solution uses the Array.Sort method with a custom comparator to sort the list, prioritizing height in descending order and the k-value in ascending order. A List is used to insert each person at the correct position based on their k-value.