Queue Reconstruction by Height

Algorithm

• Sort the ‘PEOPLE’ vector according to the comparator given below:
  • If the heights of two individuals are not equal, do:
    • Return the one with more height.
  • Else:
    • Return the one with less number of individuals required in front.
• Declare a 2-D vector ‘RESULTING_QUEUE’.
• Iterate ‘INDIVIDUAL’ from 0 to size of ‘PEOPLE’ vector, do:
  • Set ‘HEIGHT’ equal to PEOPLE[INDIVIDUAL][0].
  • Set ‘INDEX’ equal to PEOPLE[INDIVIDUAL][1].
  • Insert HEIGHT-INDEX pair in ‘RESULTING_QUEUE’ vector at index ‘INDEX’.
• Return ‘RESULTING_QUEUE’.

Program

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// Comparator for sorting 'PEOPLE' vector.
bool comparator(vector<int> individualA, vector<int> individualB)
{

  // If the heights of two individuals are not equal.
  if (individualA[0] != individualB[0])
  {

    //Return  the one with more height.
    return individualA[0] > individualB[0];
  }

  // Else return the one with less number of individuals required in front.
  return individualA[1] < individualB[1];
}

vector<vector<int>> queueReconstruction(vector<vector<int>> &people)
{

  // Sort the people from tallest to shortest using given comparator.
  sort(people.begin(), people.end(), comparator);

  // Declare a 2-D vector 'RESULTING_QUEUE'.
  vector<vector<int>> resultingQueue;

  for (int individual = 0; individual < people.size(); individual++)
  {
    int height = people[individual][0];
    int index = people[individual][1];

    // Insert HEIGHT-INDEX pair in 'RESULTING_QUEUE' vector at index 'INDEX'.
    resultingQueue.insert(resultingQueue.begin() + index, {height, index});
  }

  return resultingQueue;
}

int main()
{

  int n;

  // Input size of the 'PEOPLE' vector.
  cout << "Enter the size of the 'PEOPLE' array: ";
  cin >> n;

  cout << "Enter the height of each individual with the number of individuals ahead of the current individual:\n";
  vector<vector<int>> people(n, vector<int>(2));

  // Input every individual's attributes in 'PEOPLE' vector.
  for (int i = 0; i < n; i++)
  {
    cin >> people[i][0] >> people[i][1];
  }

  cout << "Queue:\n";

  // Calling QUEUE_RECONSTRUCTION() function to get the queue constructed as per the given input.
  vector<vector<int>> resultingQueue = queueReconstruction(people);

  // Printing the 'RESULTING_QUEUE'.
  for (int individual = 0; individual < resultingQueue.size(); individual++)
  {
    int height = resultingQueue[individual][0];
    int index = resultingQueue[individual][1];
    cout << height << " " << index << endl;
  }
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the size of the ‘PEOPLE’ array: 6
Enter the height of each individual with the number of individuals ahead of the current individual:
7 0
4 4
7 1
5 0
6 1
5 2

Output

Queue: 
5 0
7 0
5 2
6 1
4 4
7 1

Complexity Analysis

Time Complexity: Before queue reconstruction ‘PEOPLE’ vector is sorted according to the custom criteria. Sorting a vector is an O(NlogN) operation, where ‘N’ represents the size of the vector. Insertion in a vector is a linear-time operation. For every individual in ‘PEOPLE’ from 1 to ‘N’, we are inserting the pairs in a vector. So, the time complexity of the program is O(NlogN + N²) = O(N²), where ‘N’ is the size of the input stored in ‘PEOPLE’.

Space Complexity: Additional space is required to store all the individual attributes of ‘PEOPLE’. So, space complexity is O(N).

Check out this problem - Longest Subarray With Sum K 

Key Takeaways

You have successfully learned the solution for the queue reconstruction problem. Practice and try to solve some other similar problems on our practice platform Coding Ninjas Studio. If you don’t know where to start from, follow our guided paths to pave learning path. Coding Ninjas Studio offers interesting blogs like this one much more. Start your learning journey today.

Happy Coding!