406. Queue Reconstruction by Height

Queue Reconstruction by Height (LeetCode 406) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Sorting Based subpattern.

How to solve Queue Reconstruction by Height

Queue Reconstruction by Height is a Sorting-Based Greedy problem, part of Greedy Patterns. Solve greedy problems that require sorting as preprocessing step for optimal solutions.

Work towards the solution in these steps:

1. Consider how sorting the array of people might help in reconstructing the queue efficiently.
2. Think about sorting primarily by height in descending order and then by the number of taller or equal-height people in ascending order.
3. Once sorted, how can you place each person in the queue so that their 'k' value is satisfied?

The reference solution runs in O(n * sqrt(n)) time and O(n) space.

The Queue Reconstruction by Height solution and editorial walks through the full approach with reference code.

Problem statement

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] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

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] = [hj, kj] is the attributes of the jth 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 <= hi <= 106 0 <= ki < people.length It is guaranteed that the queue can be reconstructed.

Topics and companies

Topics: Greedy.

Reported in interviews at Google, Facebook.

How to practise Queue Reconstruction by Height on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * sqrt(n)) time and O(n) space.

Open Queue Reconstruction by Height in the code editor, or read the Queue Reconstruction by Height editorial for a worked solution with its approach and complexity analysis.

Where Queue Reconstruction by Height sits in the DSA pattern sheet

• Greedy Patterns pattern guide
• Sorting Based subpattern
• The full DSA patterns sheet

Problems related to Queue Reconstruction by Height

Other problems that use the same Sorting Based and Greedy Patterns techniques:

• Assign Cookies — Easy, same subpattern
• Candy — Hard, same subpattern
• Hand of Straights — Medium, same subpattern
• Lemonade Change — Easy, same subpattern
• Merge Triplets to Form Target Triplet — Medium, same subpattern
• Sort an Array — Medium, same subpattern

Queue Reconstruction by Height FAQ