# Queue Reconstruction by Height  Difficulty Level Medium
Greedy Queue

## Problem Description of Queue Reconstruction by Height  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 has a height greater than or equal to h. Write an algorithm to reconstruct the queue.

## Example  ```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]]```

## Algorithm For Queue Reconstruction by Height  1. Declare a vector “ans” of n rows and 2 columns where n is the number of people.
2. Initialize a Boolean vector “check” of size n with all values initially set to false, where check[i] represents whether we have filled the ith position or not.
3. Sort the given array in a non-decreasing manner and if the height of two people is the same then the one with the smaller K comes first.
4. Run a loop on i from 0 to n
• Initialize a “count” variable which counts the number of people with the same or greater height than the height of our current element.
• Run a loop on j from 0 to n
• If the current element is not filled yet or have the same height as height[i] then increment
• If the value of count gets more than the K of the current element, then break from this loop.
• Update the value of ans[j]=people[i].
• Update the value of check[j]=true because the jth position is occupied now.
5. Return “ans”.
Find Duplicate Subtrees

## Implementation for Queue Reconstruction by Height  ### C++ program for Queue Reconstruction by Height

```#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> reconstructQueue(vector<vector<int>> &people)
{
int n = people.size();
vector<vector<int>> ans(n);
vector<bool> check(n, false);
sort(people.begin(), people.end());
for (int i = 0; i < n; i++)
{
int count = 0;
int j = 0;
while (count < people[i])
{
if ((!check[j]) or (ans[j] == people[i]))
{
count++;
}
j++;
}
while (check[j])
{
j++;
}
ans[j] = people[i];
check[j] = true;
}
return ans;
}
int main()
{
vector<vector<int>> people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
vector<vector<int>> ans = reconstructQueue(people);
for (int i = 0; i < ans.size(); i++)
{
for (int j = 0; j < ans[i].size(); j++)
{
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
```5 0
7 0
5 2
6 1
4 4
7 1```

### JAVA program for Queue Reconstruction by Height

```import java.util.*;
public class Main
{
public static int[][] reconstructQueue(int[][] people)
{
int n = people.length;
int[][] ans=new int[n];
boolean[] check=new boolean[n];
for(int i=0;i<n;i++)
{
check[i]=false;
}
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a != b) {
return (a - b);
} else {
return (a - b);
}
}
});
for (int i = 0; i < n; i++)
{
int count = 0;
int j = 0;
while (count < people[i])
{
if ((check[j]==false) || (ans[j] == people[i]))
{
count++;
}
j++;
}
while (check[j])
{
j++;
}
ans[j] = people[i];
ans[j] = people[i];
check[j] = true;
}
return ans;
}
public static void main(String[] args) {
int[][] people={{10, 0}, {2, 0}, {2, 4}, {8, 1}, {2, 2}, {10, 1}};
int[][] ans=reconstructQueue(people);
for (int i = 0; i < ans.length; i++)
{
for (int j = 0; j < ans[i].length; j++)
{
System.out.print(ans[i][j]+" ");
}
System.out.println();
}
}
}
```
```2 0
10 0
2 2
8 1
2 4
10 1
```

## Complexity  ### Time complexity

For every person, it takes O(n) time to find its position so total time complexity is O(n^2).

### Space complexity

We took a “check” array and the “ans” array both with size n so space complexity is O(n).