30-Queue-Reconstruction-by-Height.md

Queue Reconstruction by Height

Problem Link

https://leetcode.com/problems/queue-reconstruction-by-height/

---

Pattern

• Queue
• Greedy

---

Approach

Sort by height descending and insert each person at their k index in the result list.

---

Time Complexity

O(n^2)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> res = new ArrayList<>();
        for (int[] p : people) res.add(p[1], p);
        return res.toArray(new int[res.size()][]);
    }
}