O(n lgn) solution using Segment Tree

  • 0

    k is the inversion count. Essentially, the question asks to reconstruct the array based on the inversion count of each element.

    Use a segment tree to maintain the size of empty slots. Each node has a lo and a hi s.t slot indexes belongs to [lo, hi). Go down to find the target slot, and bottom up to decrement the size of empty slots.

    from collections import defaultdict
    class Node(object):
        def __init__(self, lo, hi, cnt):
            self.lo = lo
            self.hi = hi
            self.cnt = cnt  # size of empty slots
            self.left = None
            self.right = None
        def __repr__(self):
            return repr("[%d,%d)" % (self.lo, self.hi))
    class SegmentTree(object):
        def __init__(self):
            self.root = None
        def build(self, lo, hi):
            if lo >= hi: return
            if lo == hi-1: return Node(lo, hi, 1)
            root = Node(lo, hi, hi-lo)
            root.left = self.build(lo, (hi+lo)/2)
            root.right = self.build((lo+hi)/2, hi)
            return root
        def find_delete(self, root, sz):
            :return: index
            root.cnt -= 1
            if not root.left:
                return root.lo
            elif root.left.cnt >= sz:
                return self.find_delete(root.left, sz)
                return self.find_delete(root.right,
    class Solution(object):
        def reconstructQueue(self, A):
            :type A: List[List[int]]
            :rtype: List[List[int]]
            def cmp(a, b):
                if a[0] != b[0]:
                    return a[0] - b[0]
                    return a[1] - b[1]
            st = SegmentTree()
            n = len(A)
            st.root = st.build(0, n)
            ret = [0]*n
            ret_cnt = defaultdict(int)
            for a in A:
                val, inv = a
                idx = st.find_delete(st.root, inv + 1 - ret_cnt[val])
                ret_cnt[val] += 1
                ret[idx] = a
            return ret

Log in to reply

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