Queue Reconstruction by Height – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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.
C++ Queue Reconstruction by Height LeetCode Solution
public class Solution {
public int[][] reconstructQueue(int[][] people) {
//pick up the tallest guy first
//when insert the next tall guy, just need to insert him into kth position
//repeat until all people are inserted into list
Arrays.sort(people,new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2){
return o1[0]!=o2[0]?-o1[0]+o2[0]:o1[1]-o2[1];
}
});
List<int[]> res = new LinkedList<>();
for(int[] cur : people){
res.add(cur[1],cur);
}
return res.toArray(new int[people.length][]);
}
}`
Java Queue Reconstruction by Height LeetCode Solution
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
sort(people.begin(), people.end(),[](pair<int,int> p1, pair<int,int> p2){
return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
});
vector<pair<int,int>> sol;
for (auto person : people){
sol.insert(sol.begin() + person.second, person);
}
return sol;
}
Python 3 Queue Reconstruction by Height LeetCode Solution
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# sort the people from tall to short
# insert from tall to short (insert at index = p[1])
people.sort(key=lambda p: (-p[0], p[1]))
res = []
for p in people:
res.insert(p[1], p)
return res
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1