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
class Solution {
 public:
  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    vector<vector<int>> ans;

    sort(people.begin(), people.end(), [](const auto& a, const auto& b) {
      return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    });

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

    return ans;
  }
};

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

    Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);

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

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