# Queue Reconstruction by Height
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/queue-reconstruction-by-height)
Canonical: https://scaleengineer.com/dsa/problems/queue-reconstruction-by-height
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Binary Indexed Tree, Segment Tree
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
You are given an array of people, `people`, which are the attributes of some people in a queue (not necessarily in order). Each `people[i] = [hi, ki]` represents the `ith` person of height `hi` with **exactly** `ki` other people in front who have a height greater than or equal to `hi`.

Reconstruct and return _the queue that is represented by the input array_ `people`. The returned queue should be formatted as an array `queue`, where `queue[j] = [hj, kj]` is the attributes of the `jth` person in the queue (`queue[0]` is the person at the front of the queue).

**Example 1:**

**Input:** people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
**Output:** [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
**Explanation:**
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

**Example 2:**

**Input:** people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
**Output:** [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

**Constraints:**

* `1 <= people.length <= 2000`
* `0 <= hi <= 106`
* `0 <= ki < people.length`
* It is guaranteed that the queue can be reconstructed.

# Approaches
## Brute Force by Checking All Permutations
This approach explores every possible arrangement of the people to find the one that satisfies the given conditions. It generates all permutations of the input array and, for each permutation, verifies if it represents a valid queue. This is the most straightforward but also the most computationally expensive method.
**Time:** O(N! * N^2). There are `N!` permutations to check. Validating each permutation requires iterating through the `N` people, and for each person, looking at all predecessors, resulting in an `O(N^2)` check. The total complexity is prohibitively large. · **Space:** O(N). The space is dominated by the recursion depth, which is `N`. We need to store the current permutation being built.
**Pros:** Conceptually simple to understand as it directly models the problem of finding a valid ordering.; Guaranteed to find the solution if one exists.
**Cons:** Extremely inefficient and will time out for the given constraints (`N` up to 2000).; Only feasible for very small inputs (e.g., N < 10).; Can be complex to implement correctly with backtracking.
### Explanation
The brute-force method systematically generates every possible ordering of the people in the queue. For an input of `N` people, there are `N!` (N factorial) possible permutations. For each of these permutations, we must perform a check to see if it is a valid reconstruction. The validation process involves iterating through the generated queue from front to back. For each person `p = [h, k]` at index `i`, we count the number of people `p'` at indices `j < i` who have a height `h' >= h`. If this count matches `k` for every single person in the queue, then we have found the correct arrangement. Since the problem guarantees that a solution exists, this method will eventually find it. However, the `N!` growth rate makes it impractical for anything but the smallest of inputs.
### Algorithm
- Define a recursive function, say `findSolution`, that attempts to build the queue by trying to place one person at a time from the set of unplaced people.
- The function would take the current partially built queue and the list of remaining people as arguments.
- The base case for the recursion is when all people have been placed in the queue. At this point, we have a full permutation.
- We then need a helper function, `isValid(queue)`, to verify if this permutation satisfies all conditions. This function iterates through the generated queue and for each person `[h, k]`, it checks if there are exactly `k` people before it with height greater than or equal to `h`.
- If the queue is valid, we have found our solution.
- In the recursive step, we iterate through all `remaining_people`, pick one, add it to the `current_queue`, and recurse. After the recursive call returns, we backtrack by removing the person to try other possibilities.
- This process explores the entire search space of `N!` permutations.

## Greedy Approach with Sorting and List Insertion
A much more efficient approach is to use a greedy strategy. The key insight is to place people one by one into the queue in a specific order. If we place the tallest people first, their `k` value is unaffected by any shorter people we place later. This simplifies the problem significantly, as the `k` value for a person being placed directly corresponds to their index in the partially built queue.
**Time:** O(N^2). The sorting step takes `O(N log N)`. The main cost comes from the insertions into the list. Inserting an element into a list at a specific index can take `O(N)` time in the worst case. Since we do this `N` times, the total time for insertions is `O(N^2)`, making the overall complexity `O(N^2)`. · **Space:** O(N). We use a list to store the reconstructed queue, which will hold `N` elements.
**Pros:** Significantly faster than the brute-force approach.; Relatively straightforward to implement once the sorting logic is understood.; Efficient enough to pass the given problem constraints.
**Cons:** The time complexity of O(N^2) might be too slow for problems with larger constraints, although it passes for this specific problem.; It is not the most optimal solution available.
### Explanation
This greedy algorithm hinges on a clever sorting order. By sorting people from tallest to shortest, we ensure that when we place a person `p = [h, k]`, all the people already in our reconstructed queue are taller than or equal to `p`. This is because we've only processed taller people so far. Consequently, the `k` value, which is the count of taller-or-equal people in front, simply becomes the target index for this person in the current queue. If two people have the same height, the one with the smaller `k` value must come first in the sorted list to be placed earlier. The algorithm proceeds by initializing an empty list, iterating through the sorted people, and inserting each person `[h, k]` at index `k` of the list. This insertion pushes existing elements to the right, making space. While simple, the repeated insertions into the middle of a list lead to an overall quadratic time complexity.
### Algorithm
- First, sort the `people` array. The primary sorting key is height `h` in **descending** order. The secondary sorting key for people with the same height is `k` in **ascending** order.
- Create an empty list or dynamic array to serve as the reconstructed queue (e.g., a `LinkedList` in Java).
- Iterate through the sorted `people` array one by one.
- For each person `p = [h, k]`, insert them into the queue at the index specified by their `k` value. For example, if `p = [7, 1]`, it gets inserted at index 1 of the current list.
- After all people have been inserted, the list will represent the correctly reconstructed queue. Convert this list back into a 2D array and return it.

## Optimal Greedy Approach with a Segment Tree
This approach builds upon the greedy sorting strategy but optimizes the process of finding the correct insertion position. Instead of a linear-time insertion into a list, it uses a more advanced data structure like a Segment Tree or a Binary Indexed Tree (BIT) to find the k-th available slot in logarithmic time, leading to a more efficient overall solution.
**Time:** O(N log N). Sorting takes `O(N log N)`. For each of the `N` people, we perform a query and an update on the data structure, both of which take `O(log N)`. This results in a total time of `O(N log N + N log N) = O(N log N)`. · **Space:** O(N). We need `O(N)` space for the result array and `O(N)` space for the Segment Tree or BIT (an array-based Segment Tree typically requires `4N` space).
**Pros:** The most efficient solution with a time complexity of `O(N log N)`.; Scales well to larger inputs beyond the current constraints.; Demonstrates proficiency with advanced data structures.
**Cons:** Significantly more complex to implement than the `O(N^2)` list insertion method.; The overhead and constant factors of the data structure might make it slower for small `N` in practice.
### Explanation
This optimal approach uses the same greedy sorting strategy (tallest to shortest, then by `k`) but addresses the `O(N^2)` bottleneck of list insertions. The problem of finding the `k`-th position to insert into can be rephrased as finding the `k`-th empty slot in the final queue. A Segment Tree can be built to maintain the count of empty slots over ranges of indices. For each person `[h, k]`, we query this tree to find the index of the `(k+1)`-th empty slot. This query can be performed in `O(log N)` time by traversing the tree from the root. Once the index is found, we place the person in our result array and update the tree to mark that slot as occupied, which is also an `O(log N)` operation. By repeating this for all `N` people, the total time for placement becomes `O(N log N)`, making the entire algorithm's complexity dominated by the initial sort.
### Algorithm
- Sort the `people` array using the same logic as the previous approach: height descending, then `k` ascending.
- Create an empty result array `queue` of size `N`.
- Build a data structure, such as a Segment Tree or a Binary Indexed Tree (BIT), over the indices `0` to `N-1`. This structure will be used to keep track of the empty slots in the `queue` array. Initialize it so that each slot is marked as empty (e.g., value `1`).
- Iterate through the sorted `people` array. For each person `p = [h, k]`:
  - Query the data structure to find the index `j` of the `(k+1)`-th empty slot. This operation takes `O(log N)` time.
  - Place the person `p` in the result array at this found index: `queue[j] = p`.
  - Update the data structure to mark slot `j` as filled (e.g., change its value to `0`). This also takes `O(log N)` time.
- After processing all people, return the `queue` array.

# Solutions
### Java

```java
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[]> ans = new ArrayList<>(people.length);
    for (int[] p : people) {
      ans.add(p[1], p);
    }
    return ans.toArray(new int[ans.size()][]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
    sort(people.begin(), people.end(),
         [](const vector<int> &a, const vector<int> &b) {
           return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
         });
    vector<vector<int>> ans;
    for (const vector<int> &p : people)
      ans.insert(ans.begin() + p[1], p);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: people . sort(key=lambda x: (- x[0], x[1])) ans = [] for p in people: ans . insert(p[1], p) return ans

```