# Python solution with detailed explanation

• Solution

Queue Reconstruction by Height https://leetcode.com/problems/queue-reconstruction-by-height/

Problem Insights

1. Think about the shortest person. Say his height is 4 and his k value is also 4. In the reconstructed queue, what index should he be at? The answer is at index k since there are k people with height greater than equal to h.
2. So say we remove the shortest person, solve the problem, and then add the shortest person - we are done. Example:[[5,0], [7,0], [5,2], [6,1], [7,1]] - Without [4,4] (the smallest height). Now 4,4 can be inserted into its index.
3. What about the sub-problem? Again remove the shortest persons [5,0] and [5,2], solve the remaining problem and insert shortest problem.

Algorithm

1. Find the tallest people and sort them by their k value. Their k value must be either 0, 1, 2, 3.. since their k value is exclusively derived by "people of height equal" since no one is available with a greater height.
2. Now find the next tallest person. Sort them by their k value and insert them into the list using k value as index. The k value acts as their rank.
3. Repeat the process.
``````class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
people_dict = {}
for p in people:
h,k = p[0], p[1]
people_dict.setdefault(h, [])
people_dict[h].append(k)
result = []
for h in sorted(people_dict.keys(), reverse=True):
people_dict[h].sort()
for k in people_dict[h]:
result.insert(k, [h,k])
return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.