Table of Contents

## 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

- Declare a vector “ans” of n rows and 2 columns where n is the number of people.
- Initialize a Boolean vector “check” of size n with all values initially set to false, where check[i] represents whether we have filled the i
^{th}position or not. - 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.
- 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 j
^{th}position is occupied now.

- Return “ans”.

## 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][1]) { if ((!check[j]) or (ans[j][0] == people[i][0])) { 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][2]; 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[0] != b[0]) { return (a[0] - b[0]); } else { return (a[1] - b[1]); } } }); for (int i = 0; i < n; i++) { int count = 0; int j = 0; while (count < people[i][1]) { if ((check[j]==false) || (ans[j][0] == people[i][0])) { count++; } j++; } while (check[j]) { j++; } ans[j][0] = people[i][0]; ans[j][1] = people[i][1]; 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).