Skip to content

406. Queue Reconstruction by Height 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    vector<vector<int>> ans;

    ranges::sort(people, ranges::less{}, [](const vector<int>& person) {
      const int h = person[0];
      const int k = person[1];
      return pair<int, int>{-h, k};
    });

    for (const vector<int>& person : people)
      ans.insert(ans.begin() + person[1], person);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public int[][] reconstructQueue(int[][] people) {
    List<int[]> ans = new ArrayList<>();

    Arrays.sort(people, Comparator.comparingInt((int[] person) -> - person[0])
                            .thenComparingInt((int[] person) -> person[1]));

    for (final int[] person : people)
      ans.add(person[1], person);

    return ans.stream().toArray(int[][] ::new);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def reconstructQueue(self, people: list[list[int]]) -> list[list[int]]:
    ans = []

    people.sort(key=lambda x: (-x[0], x[1]))

    for person in people:
      ans.insert(person[1], person)

    return ans