
Problem Statement
In this problem, we are provided with an array people
, where each element people[i]
consists of a pair [hi, ki]
. Here, hi
denotes the height of the i-th
person, and ki
represents the number of individuals standing in front of this person who are of equal or greater height than hi
. The objective is to reconstruct the queue from this unordered list. Each element in the output queue, queue[j] = [hj, kj]
, must satisfy the criteria that there are exactly kj
people in front of person j
with height hj
or taller. The goal is to return this reconstructed queue as an array where queue[0]
is the front of the queue.
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]]
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.
Approach and Intuition
The problem requires reconstructing the queue based on height and the count of people taller or of the same height standing in front. This is a sorting and placement problem where understanding the interdependencies of array items (heights and counts) is crucial.
Sort and Insert Approach:
- First, sort the people array in descending order based on height
h
. If two people have the same height, sort them by increasing order ofk
. - Once sorted, initialize an empty list
queue
. - For each person
[h, k]
from the sorted list, insert them into thequeue
at the indexk
. In Python, this can be done usingqueue.insert(k, [h, k])
. - The rationale behind insertion at index
k
is that there should be exactlyk
people before this person who are of the same or greater height. - By placing the tallest people first, we ensure that inserting subsequent people does not affect the counts of those already placed.
- First, sort the people array in descending order based on height
Visualization and Examples:
- In example 1, start by sorting
people
resulting in[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
. - Start inserting from the sorted array: place
[7, 0]
at index0
, and so on. Each insertion respects the positional requirements dictated byk
. - For example 2, after sorting and inserting in similar fashion, the structure of the queue gradually builds up correctly without violating the
k
constraints.
- In example 1, start by sorting
By using this sort and insertion methodology, each placement ensures the condition that the number of people standing in front with equal or greater height matches the k
value of the person being placed, satisfying the problem's constraints and requirements.
Solutions
- Java
class Solution {
public int[][] arrangeQueue(int[][] queue) {
Arrays.sort(queue, new Comparator<int[]>() {
@Override
public int compare(int[] item1, int[] item2) {
return item1[0] == item2[0] ? item1[1] - item2[1] : item2[0] - item1[0];
}
});
List<int[]> result = new LinkedList<>();
for(int[] person : queue){
result.add(person[1], person);
}
int length = queue.length;
return result.toArray(new int[length][2]);
}
}
The solution provided is a Java implementation for reconstructing a queue based on height and the number of people in front of an individual who have an equal or greater height.
- Start with sorting the given array of people using a custom comparator. The array
queue
contains elements wherequeue[i][0]
is the height of the person andqueue[i][1]
is the count of people taller or of the same height standing in front of this person. - The comparator prioritizes by height (descending order), and, if the heights are equal, it sorts by the count of people in ascending order.
- Initialize a
LinkedList
to facilitate easier insertions at specific indices as you iterate through the sorted array. - For each person in the sorted array, insert them into the
LinkedList
at the index specified by their count (i.e.,person[1]
), effectively placing them in the correct position relative to those already inserted. - Convert the
LinkedList
to a 2D array matching the dimensions of the inputqueue
and return this as the final reconstructed queue.
By sorting the people by height and then respecting the count of people in front, this approach efficiently reconstructs the order in which people should stand to satisfy the given conditions.
No comments yet.