# O(n lgn) solution using Segment Tree

• `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)
else:
return self.find_delete(root.right,
sz-root.left.cnt)

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]
else:
return a[1] - b[1]

st = SegmentTree()
n = len(A)
st.root = st.build(0, n)
A.sort(cmp=cmp)
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
``````

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