Queue Reconstruction by Height
MedPrompt
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 <= 20000 <= hi <= 1060 <= ki < people.length- It is guaranteed that the queue can be reconstructed.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every possible arrangement of the people to find the one that satisfies the given conditions. It generates all permutations of the input array and, for each permutation, verifies if it represents a valid queue. This is the most straightforward but also the most computationally expensive method.
Algorithm
- Define a recursive function, say
findSolution, that attempts to build the queue by trying to place one person at a time from the set of unplaced people. - The function would take the current partially built queue and the list of remaining people as arguments.
- The base case for the recursion is when all people have been placed in the queue. At this point, we have a full permutation.
- We then need a helper function,
isValid(queue), to verify if this permutation satisfies all conditions. This function iterates through the generated queue and for each person[h, k], it checks if there are exactlykpeople before it with height greater than or equal toh. - If the queue is valid, we have found our solution.
- In the recursive step, we iterate through all
remaining_people, pick one, add it to thecurrent_queue, and recurse. After the recursive call returns, we backtrack by removing the person to try other possibilities. - This process explores the entire search space of
N!permutations.
Walkthrough
The brute-force method systematically generates every possible ordering of the people in the queue. For an input of N people, there are N! (N factorial) possible permutations. For each of these permutations, we must perform a check to see if it is a valid reconstruction. The validation process involves iterating through the generated queue from front to back. For each person p = [h, k] at index i, we count the number of people p' at indices j < i who have a height h' >= h. If this count matches k for every single person in the queue, then we have found the correct arrangement. Since the problem guarantees that a solution exists, this method will eventually find it. However, the N! growth rate makes it impractical for anything but the smallest of inputs.
Complexity
Time
O(N! * N^2). There are `N!` permutations to check. Validating each permutation requires iterating through the `N` people, and for each person, looking at all predecessors, resulting in an `O(N^2)` check. The total complexity is prohibitively large.
Space
O(N). The space is dominated by the recursion depth, which is `N`. We need to store the current permutation being built.
Trade-offs
Pros
Conceptually simple to understand as it directly models the problem of finding a valid ordering.
Guaranteed to find the solution if one exists.
Cons
Extremely inefficient and will time out for the given constraints (
Nup to 2000).Only feasible for very small inputs (e.g., N < 10).
Can be complex to implement correctly with backtracking.
Solutions
Solution
class Solution {public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, (a, b)->a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]); List<int[]> ans = new ArrayList<>(people.length); for (int[] p : people) { ans.add(p[1], p); } return ans.toArray(new int[ans.size()][]); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.