Worse case O(n^2) and O(nlogn) in average using binary tree travel


  • 7

    The main idea is as follows:

    1. Sort the array with h descending and if the height equal sorted with k ascending.
    2. Building the binary tree as following rules:
      2.1 using the first sorted people as root
      2.2 iterate insert the people.
      if the k of current people less than the root, insert the people in the left node, and increase the root with 1. It means that how many people preceding the root when doing inorder travel.
      Otherwise, insert the node to the right. At the same time, you need to decrease the node k with k-root.val which means the preceding already has k in the left subtree.
    3. Inorder travel the tree to get the final result.

    NOTE: For the sort, why we should sort the value with same height in ascending? if not, the node with same height can't order correctly. It's possible that the node with less k(height count) could be preceding the node with more k. EX: (5,3), (5,2). The (5,3) could be preceding (5,2).

    class Node(object):
        def __init__(self,p):
            """
            For general programming, it's better to create Person class.
            """
            self.person=p
            self.hcnt=1
            self.left=None
            self.right=None
    
    class Solution(object):
        def reconstructQueue(self,people):
            if not people:
                return []
            # sort the people with height descending
            # if height equal sort with hcnt ascending
            people.sort(cmp=lambda x,y:y[0]-x[0] if x[0]!=y[0] else x[1]-y[1])
            root=Node(people[0])
            for p in people[1:]:
                self.insert(root,p,p[1])
            res=[]
            self.inorder(root,res)
            return res
                
        def insert(self,root,p,hcnt):
            # compare the height cnt with root
            # if the hight count less than the root, go to the left
            if hcnt<root.hcnt:
                if not root.left:
                    root.left=Node(p)
                else:
                    self.insert(root.left,p,hcnt)
                # increase the root cnt,means number preceding in the left subtree
                root.hcnt+=1
            else:
                if not root.right:
                    root.right=Node(p)
                else:
                    # decrease the hcnt since it already has root.cnt before the left subtree
                    self.insert(root.right,p,hcnt-root.hcnt)
                    
        def inorder(self,root,res):
            if not root:
                return 
            self.inorder(root.left,res)
            res.append(root.person)
            self.inorder(root.right,res)
    

Log in to reply
 

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