Queue Reconstruction by Height

LeetCode Problem #406 (Medium)

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.

Note:

The number of people is less than 1,100.

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.

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.

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.

Time Complexity: O(n^2)

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

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;
}