Queue Reconstruction by Height

Difficulty Level Medium
Frequently asked in Amazon Apple ByteDance Facebook Google
Greedy QueueViews 2567

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”.

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).

References

Translate »