Queue Reconstruction by Height

Medium

Google

5 views

Topics:

ArraysGreedy Algorithms

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [h_i, k_i] represents the i^th person of height h_i with exactly k_i other people in front who have a height greater than or equal to h_i.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [h_j, k_j] is the attributes of the j^th person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

1 <= people.length <= 2000
0 <= h_i <= 10⁶
0 <= k_i < people.length
It is guaranteed that the queue can be reconstructed.

Try coding it in LeetCode

Queue Reconstruction by Height

Medium

Google

5 views

Topics:

ArraysGreedy Algorithms

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [h_i, k_i] represents the i^th person of height h_i with exactly k_i other people in front who have a height greater than or equal to h_i.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [h_j, k_j] is the attributes of the j^th person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

1 <= people.length <= 2000
0 <= h_i <= 10⁶
0 <= k_i < people.length
It is guaranteed that the queue can be reconstructed.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the height and k values (people[i][0] and people[i][1])? Can they be negative?
Is the input array `people` guaranteed to be non-null and non-empty? What should I return if it's null or empty?
Can there be duplicate height values in the input array? If so, how should I handle them regarding the 'k' value and the final reconstructed queue?
Is it guaranteed that a valid reconstruction of the queue always exists, given the input constraints?
What is the data type of the output? Should it be a new array, or can I modify the input array in-place?

Brute Force Solution

Approach

The brute force approach to reconstructing the queue involves trying every possible arrangement of people. We systematically place each person one at a time, checking if their placement satisfies the given conditions. If it does, we continue, otherwise, we backtrack and try a different arrangement.

Here's how the algorithm would work step-by-step:

Start with an empty queue.
Consider the first person and try placing them in every possible position in the queue, from the beginning to the end.
For each position, check if the number of taller or equal height people in front of them matches their specified count.
If the count matches, move on to the next person and repeat the placement process.
If the count doesn't match, try the next available position for the current person.
If all possible positions for a person are exhausted without a match, backtrack to the previous person and try a different position for them.
Continue this process until all people have been placed and their conditions are met.
The first arrangement that satisfies all the conditions for everyone is the reconstructed queue.

Code Implementation

def reconstruct_queue_brute_force(people):
    number_of_people = len(people)
    reconstructed_queue = []
    result = []

    def solve(index):
        nonlocal result
        if index == number_of_people:
            result = reconstructed_queue[:]
            return True

        person_height = people[index][0]
        people_in_front = people[index][1]

        for position in range(len(reconstructed_queue) + 1):
            reconstructed_queue.insert(position, people[index])

            # Validate the reconstructed queue at this index
            taller_or_equal = 0
            for i in range(position):
                if reconstructed_queue[i][0] >= person_height:
                    taller_or_equal += 1

            # Backtrack if the current arrangement is invalid.
            if taller_or_equal != people_in_front:
                reconstructed_queue.pop(position)
                continue

            # Recursively try placing the next person.
            if solve(index + 1):
                return True

            # Backtrack after recursive call returns
            reconstructed_queue.pop(position)

        return False

    solve(0)
    return result

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach explores all possible permutations of the n people to reconstruct the queue. Placing the first person has n possible positions. Placing the second person has n-1 possible positions, and so on. This leads to n * (n-1) * (n-2) * ... * 1 = n! (n factorial) possible arrangements to check in the worst case. For each arrangement, we need to validate if it satisfies the given constraints, which takes O(n) time. Therefore, the overall time complexity is O(n! * n), which simplifies to O(n!).

Space Complexity

O(N) – The brute force approach described uses an initially empty queue which gradually gets populated with people. In the worst-case scenario, all N people will be added to this queue. Backtracking may involve temporarily removing elements, but the queue's maximum size remains bounded by N. Therefore, the auxiliary space required to store this queue is directly proportional to N.

Optimal Solution

Approach

The key to solving this problem efficiently is to think about the people from tallest to shortest. By placing taller people first, we can easily figure out where the shorter people should go without messing up the taller people's positions.

Here's how the algorithm would work step-by-step:

Begin by organizing the people from tallest to shortest. If there are multiple people with the same height, sort them based on how many people are supposed to be in front of them (from fewest to most).
Now, build the queue one person at a time, starting with the tallest. The number of people that are supposed to be in front of each person will guide the placement of that person. For example, if someone should have two people in front of them, put that person in the third available slot.
Since we process the people in order from tallest to shortest, when we place a shorter person, it won't affect the positions of any of the taller people already in the queue.
Continue until everyone is placed, and the queue is reconstructed.

Code Implementation

def reconstruct_queue(people):
    # Sort people by height (descending) and k value (ascending).
    people.sort(key=lambda x: (-x[0], x[1]))

    reconstructed_queue = []

    # Insert each person at the index specified by their k value.
    for person in people:
        index_to_insert = person[1]

        # Inserting at the correct index is crucial.
        reconstructed_queue.insert(index_to_insert, person)

    # Return the reconstructed queue.
    return reconstructed_queue

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first sorts the input array of n people, which takes O(n log n) time. Then, it iterates through each person (n times) and inserts them into the correct position in the result list. Inserting at a specific index in a list of size i takes O(i) time in the worst case (when inserting at the beginning, shifting all other elements). Thus, inserting n elements will result in worst case 1 + 2 + 3 + ... + n which sums to n(n+1)/2. Therefore insertion operation is O(n²). The sorting cost O(n log n) is dominated by the insertion loop O(n²), so the overall time complexity is O(n²).

Space Complexity

O(N) – The algorithm reconstructs the queue by inserting people into a new list, where N is the number of people in the input. This new list, representing the reconstructed queue, requires space proportional to the number of people. Therefore, the auxiliary space used is directly proportional to the input size N. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list to signify no reconstruction possible.
Input array with one element	Return the input array as is, as it is already trivially reconstructed.
All people have the same height and k values are sorted ascending	The algorithm must insert them sequentially at indices 0, 1, 2, etc.
All people have the same height and k values are sorted descending	The algorithm must insert them sequentially at indices k, k, k, etc. which might cause issues with re-insertion.
People with the same height but different k values	Sort by height descending, then k ascending to resolve conflicts during insertion.
Large input array (performance implications)	Choose an efficient sorting algorithm (e.g., merge sort or quicksort) for the initial sort to avoid quadratic time complexity.
k value is out of bounds (k < 0 or k >= n)	Throw an IllegalArgumentException or return null as this is an invalid input.
Integer overflow when calculating indices (if using cumulative sums or similar)	Use long data type to avoid overflow when summing or calculating indices.