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.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.LinkedList;
4import java.util.List;
5
6public class Solution {
7 public int[][] reconstructQueue(int[][] people) {
8 Arrays.sort(people, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : b[0] - a[0]);
9 List<int[]> result = new LinkedList<>();
10 for (int[] p : people) {
11 result.add(p[1], p);
12 }
13 return result.toArray(new int[people.length][2]);
14 }
15
16 public static void main(String[] args) {
17 Solution sol = new Solution();
18 int[][] people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
19 int[][] result = sol.reconstructQueue(people);
20
21 for (int[] person : result) {
22 System.out.print("[" + person[0] + ", " + person[1] + "] ");
23 }
24 }
25}In this Java solution, the Arrays.sort method is used with a custom comparator to sort the input list first by height in descending order, and then by the number of people in ascending order. It utilizes a LinkedList to insert elements at specified indices efficiently.