Python solution with detailed explanation


  • 1
    G

    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
    

Log in to reply
 

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