# Queue Reconstruction by Height

## Problem Statement

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers `(h, k)`, where `h` is the height of the person and `k` is the number of people in front of this person who have a height greater than or equal to `h`. Write an algorithm to reconstruct the queue.

{% hint style="info" %}
Note:

The number of people is less than 1,100.
{% endhint %}

## Testcase

```
Input:
[[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]]
```

## Problem Explanation

In this problem, we are given a two-dimensional vector containing pairs of integers which describe two attributes of a person standing in a queue—height (h) and number of people standing in front of them who are taller than them (k).

#### Example:

Consider the queue: \[\[7,0], \[4,4], \[7,1], \[5,0], \[6,1], \[5,2]]

```
Person 1: Height = 7, 0 taller people in front
Person 2: Height = 4, 4 taller people in front
Person 3: Height = 7, 1 taller person in front
Person 4: Height = 5, 0 taller people in front
Person 5: Height = 6, 1 taller person in front
Person 6: Height = 5, 2 taller people in front
```

## Prerequisite Knowledge

### Insertion Sort

This is an in-place comparison-based sorting algorithm where a sorted sub-list is maintained and every consecutive element which is compared must find its appropriate position within the sorted sub-list. In effect, it is as though each element "inserts" itself in the correct position during every iteration.

{% code title="Algorithm" %}

```
The first element is already considered sorted, so return 1.
Choose the next element and compare it with all the elements in the sorted sub-list.
Shift the elements in the sorted sub-list which are greater than the inserted element.
Insert the element.
Repeat until list is sorted.
```

{% endcode %}

## Algorithm

### Insertion Sort Approach

In this approach, we perform in-place sorting by taking two parameters of comparison into consideration. 

At each iteration, the first value in the vector, which is the height value, is sorted in descending order since the problem allows for taller people to stand in front of shorter people. 

If the height values are equal, we compare the second value in the vector, which is the number of people standing in front of the particular person, in ascending order.

1. Initialize an empty vector to insert each person.
2. Compare each person such that

   a. If they do not have the same height (h) value, they should be sorted in descending order.

   b. If they have the same height (h) value, sort them in ascending order of the number of people in front of them (k).
3. Insert each person into position k. 

{% hint style="info" %}
Time Complexity: O(n^2)
{% endhint %}

### Illustration

* In the first pass, we consider the first vector \[7, 1]. The first element is considered to be sorted already, so we place it at position 0.

```
[[7, 1]]
```

* In the second pass, we look for a vector with a h value less than 7 in order to sort in descending order. We take vector \[7, 0], but since the h value is the same as vector \[7, 1], we consider the k value and sort in ascending order, placing \[7, 1] at position 1.

```
[[7, 0], [7, 1]]
```

* In the third pass, we choose vector \[6, 1] and place it at position 1.

```
[[7, 0], [6, 1], [7, 1]]
```

* In the fourth pass, we choose vector \[5, 0] and place it at position 0.

```
[[5, 0], [7, 0], [6, 1], [7, 1]]
```

* In the fifth pass, we choose vector \[5, 2] and place it at position 2.

```
[[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]
```

* In the final pass, we chose vector \[4, 4] and place it at position 4 to obtain the final output.

```
[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
```

## Code

```cpp
static bool compare(v ector<int>& v1, vector<int>& v2) {
    // Check if the two h values are different
    // Check if the people have been sorted in ascending order of h value
    if(v1[0] != v2[0]) {
        return v1[0] > v2[0];
    }
    // If the h values are the same, compare the k values and sort in descending order
    else {
        return v1[1] < v2[1];
    }
}

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    // Sort the vector of people 
    sort(people.begin(), people.end(), compare);
    // Initialize a resultant vector
    vector<vector<int>> res;
    int n = people.size();
    // Insert each person into position k
    for(int i = 0; i < n; i++) {
        res.insert(res.begin() + people[i][1], people[i]);
    }
    return res;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-1/queue-reconstruction-by-height.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.