#406

Medium

auto_awesomeArray plus Binary Indexed Tree

LeetCode Problem Workspace

Queue Reconstruction by Height

Reconstruct a queue based on the given heights and the number of taller people in front, using sorting and binary indexed trees.

array binary indexed tree segment tree sorting

Problem Statement

You are given an array of people, where each element represents a person with two values: height and the number of people in front who are taller or the same height. Your task is to reconstruct the queue such that each person’s position satisfies both their height and the number of taller people in front of them.

The input consists of an array where each person is represented by [height, k]. Your goal is to return the reconstructed queue as an array, ensuring that each person in the queue satisfies the condition based on their height and the number of people taller than or equal to them in front.

Examples

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

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

Example details omitted.

Constraints

1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
It is guaranteed that the queue can be reconstructed.

Solution Approach

Sort by Height and Position

Start by sorting the people array by height in descending order. This ensures that the tallest people are considered first. For people of the same height, sort by the number of people in front (k) in ascending order to ensure that those with fewer people in front get placed first.

Insert into Queue Using Binary Indexed Tree

For each person in the sorted list, use a binary indexed tree (BIT) to track the available positions. This will help in efficiently finding the right position for each person based on the number of taller people already placed.

Reconstruct the Queue

Using the binary indexed tree, place each person in the correct position by checking the available spots. Update the BIT as you place each person to ensure subsequent people have access to correct available positions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The sorting step takes O(n log n), where n is the length of the people array. The insertion process for each person takes O(log n) due to the binary indexed tree. Overall, the time complexity is O(n log n), with space complexity depending on the binary indexed tree used, which is O(n).

What Interviewers Usually Probe

Look for understanding of sorting and binary indexed trees.
Check if the candidate can explain the interaction between sorting and efficient placement using BIT.
Evaluate how the candidate optimizes for time complexity, particularly with larger inputs.

Common Pitfalls or Variants

Common pitfalls

Not understanding the need for sorting the array by height before inserting people into the queue.
Failing to use the binary indexed tree efficiently for tracking available positions.
Inserting people into incorrect positions due to not properly considering the 'k' value in the sorting step.

Follow-up variants

Changing the sorting order of people, such as sorting by height in ascending order first.
Optimizing the binary indexed tree for different constraints or array sizes.
Modifying the problem by including additional attributes for each person, such as age, to be taken into account during the reconstruction.

FAQ

How do I efficiently reconstruct the queue by height?

Sort the people array by height in descending order, and then use a binary indexed tree to efficiently track available positions while placing people.

What is the role of the binary indexed tree in this problem?

The binary indexed tree (BIT) is used to track available positions in the queue and ensures efficient placement of each person based on the number of taller people already in front.

How does the sorting step help in reconstructing the queue?

Sorting the array by height first ensures that the tallest people are placed first, and the secondary sorting by the number of taller people in front guarantees the correct position for each person.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting and binary indexed tree operations, where n is the number of people in the input array.

Can the queue reconstruction be done without sorting?

No, sorting by height is crucial to ensure the correct order of placement, especially when handling multiple people of the same height.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        ans = []
        for p in people:
            ans.insert(p[1], p)
        return ans

Continue Practicing

#327 count of range sum #493 reverse pairs #315 count of smaller numbers after self