python solution with detailed explanation. 90+


  • 0
    F

    #we have list of persons represented as [height, key] as input
    #First fill the answer list with the tallest persons in ascending order of their keys eg: [7,0], [7,1], [7,2]
    #Then fill the next tallest persons in the answer list at index same as key. eg: [7,0],[6,1],[7,1],[7,2],[6,5]
    #so on

    more explanation:

    #First sort the input list in descending order of heights and ascending order of keys
    #now iterate over the list and insert each person into answer array at index same as key of person.

    eg: input : [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    sort input: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
    iterate over sorted array and insert each person at index same as key of the person
    answer array grows like this for each iteration.
    [[7,0]]
    [[7,0],[7,1]]
    [[7,0],[6,1],[7,1]]
    [[5,0],[7,0],[6,1],[7,1]]
    [[5,0],[7,0],[5,2],[6,1],[7,1]]
    [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] -- final answer

    def reconstructQueue(self, people):
    ans = []
    if people:
    people.sort(key = lambda x: (x[0],-1*x[1]), reverse = True)
    for p in people:
    ans.insert(p[1], p)
    .return ans


Log in to reply
 

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