Python: binary tree with successor/predecessor queries and hierarchical gap tracking
Intuition\n Describe your first thoughts on how to solve this problem. \nBinary trees have O(\log N) successor/predecessor queries, so should be able to track p
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBinary trees have $$O(\\log N)$$ successor/predecessor queries, so should be able to track possible insertions.  \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n* Build a binary tree of all insertions and the size of the first gap to the left, the largest gap to the left below it in the tree, and the largest gap below it in the tree (left or right).\n* Insert blockers as they come, update predecessor & successor with new gap sizes, and propagate those changes in the insert() recursion.\n* Queries work by either:\n    * Insert the query key in the tree if it\'s not there.\n    * Find the largest gap to the left of the query key efficiently using a successor/predecessor query, along with the largset gap to the left & largest gap below in a recursion.\n    * Delete the query key if it was added during the query.\n\nTo avoid the tree getting too imbalanced, use an amortization strategy that rebuild the tree every $$N$$ insertions.\n\nThat all worked, and has $$O(N\\log N)$$ complexity, but was still too slow in python (time limit).\n\nAfter reading some solutions, I rewrote to use the back-to-front query method a lot of the top solutions use:\n* Build the all-blockers tree in random order to get a balanced tree (balanced w.h.p.)\n* delete blockers as we walk back in the list\n* Very similar tracking gaps and updating them\n    * Hierarchical gap tracking is implemented in the delete()\n* similar query, without the succ/pred query.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(N\\log N)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(N)$$\n\n# Code\n```\nimport random\n\nclass Node:\n    def __init__(self, key, left_gap):\n        self.key  = key\n        self.left = None\n        self.right = None\n        self.gap_to_left = left_gap\n        self.largest_gap_to_left = None\n        self.largest_gap_below = None\n\n\ndef print_tree(node, depth=0):\n    if node is None:\n        return\n    print("  " * depth, node.key)\n    print("  " * depth, " gap_to_left:", node.gap_to_left)\n    print("  " * depth, " largest_gap_to_left:", node.largest_gap_to_left)\n    print("  " * depth, " largest_gap_below:", node.largest_gap_below)\n    if node.left is not None:\n        print("  " * depth, " left:")\n        print_tree(node.left, depth + 1)\n    if node.right is not None:\n        print("  " * depth, " right:")\n        print_tree(node.right, depth + 1)\n\n\ndef find_predecessor_successor(node, key, pre=None, suc=None):\n    # basecase\n    if node is None:\n        return (pre, suc)\n\n    # If key is at the current node\n    if node.key == key:\n        # the rightmost node of the left tree is the predecessor\n        if node.left is not None:\n            pre = node.left\n            while pre.right: pre = pre.right\n\n        # the leftmost node of the right tree is the sucessor\n        if node.right is not None:\n            suc = node.right\n            while suc.left: suc = suc.left\n\n        return pre, suc\n\n    # recursions - the root will be a possible predecessor or successor\n    if node.key > key:\n        return find_predecessor_successor(node.left, key, pre=pre, suc=node)\n    else:\n        return find_predecessor_successor(node.right, key, pre=node, suc=suc)\n\ndef update_gaps(node):\n    node.largest_gap_to_left = max(node.gap_to_left,\n                                   node.left.largest_gap_below if node.left is not None else 0)\n    node.largest_gap_below = max(node.largest_gap_to_left,\n                                 node.right.largest_gap_below if node.right is not None else 0)\n    \ndef insert(node, key, left_gap):\n    if node is None:\n        node = Node(key, left_gap)\n    elif key < node.key:\n        node.left = insert(node.left, key, left_gap)\n    else:\n        node.right = insert(node.right, key, left_gap)\n    update_gaps(node)        \n    return node\n\n\ndef delete(node, key):\n    if node is None:\n        return node\n    if key < node.key:\n        node.left = delete(node.left, key)\n    elif key > node.key:\n        node.right = delete(node.right, key)\n    else:\n        # if node is a leaf node\n        if node.left is None and node.right is None:\n            node = None\n        # if root has one left child\n        elif node.left is None:\n            node = delete(node.right, key)\n        # if node has one right child\n        elif node.right is None:\n            node = delete(node.left, key)\n        # if node has both left and right child\n        else:\n            _, successor = find_predecessor_successor(node.right, key)\n            node.key = successor.key\n            node.gap_to_left = successor.gap_to_left\n            node.right = delete(node.right, successor.key)\n    if node is not None:\n        update_gaps(node)\n    return node\n\n\n\ndef check_can_insert(node, key, sz, lo=0):\n    # basecase - empty tree\n    if node is None:\n        return key - lo >= sz\n\n    if key == node.key:\n        return node.largest_gap_to_left >= sz\n    elif key > node.key:\n        if node.largest_gap_to_left >= sz:\n            return True\n        return check_can_insert(node.right, key, sz, lo=node.key)\n    else:  # key < node.key\n        # fits in top node\'s gap?\n        if key - (node.key - node.gap_to_left) >= sz:\n            return True\n        if node.largest_gap_to_left < sz:\n            return False\n        return check_can_insert(node.left, key, sz, lo=lo)\n\n\n\n\n\ndef doit(queries):\n    results = []\n    tree = None\n\n    # precompute all blockers and gaps to their left\n    inserts = sorted([q[1] for q in queries if q[0] == 1])\n    if len(inserts) > 0:\n        gaps = [inserts[0]] + [b - a for a, b in zip(inserts, inserts[1:])]\n        paired = list(zip(inserts, gaps))\n        # random order is balanced w.h.p.\n        random.shuffle(paired)\n        for k, g in paired:\n            tree = insert(tree, k, g)\n\n    # process in reverse order\n    for q in queries[::-1]:\n        if q[0] == 1:\n            pred, succ = find_predecessor_successor(tree, q[1])\n            if succ is not None:\n                # grow gap\n                succ.gap_to_left = succ.key - (pred.key if pred is not None else 0)\n            # then delete node\n            tree = delete(tree, q[1])\n            if succ is not None:\n                update_gaps(succ)            \n        else:\n            if tree is not None:\n                results.append(check_can_insert(tree, q[1], q[2]))\n            else:\n                results.append(q[2] <= q[1])\n    return results[::-1]\n\n\nclass Solution(object):\n    def getResults(self, queries):\n        """\n        :type queries: List[List[int]]\n        :rtype: List[bool]\n        """\n        return doit(queries)\n```
['Python']