LeetCode: 315. Count of Smaller Numbers After Self

 

Several solutions and short analysis of each one.

1. List + Binary Search

The most straightforward solution, however, time complexity is O(N**2).

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        from bisect import insort, bisect_left
        arr = []
        count = []
        for i in range(len(nums) - 1, -1, -1):
            num = nums[i]
            idx = bisect_left(arr, num)
            count.append(idx)
            insort(arr, num)
        return count[::-1]

 

2. Merge Sort

Basically, "# of elements on the rightside that are smaller than the current value" equals "# of movements in stable sort". This solution uses the above fact. Time complexity is O(NlogN).

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        self.nums = nums
        self.count = [0] * len(nums)
        tobesorted = [i for i in range(len(nums))]
        self.merge_sort(tobesorted, 0, len(nums)-1)
        return self.count
        
    def merge_sort(self, arr, left, right):
        if left == right:
            return [arr[left]]
        mid = (left + right) // 2
        larr = self.merge_sort(arr, left, mid)
        rarr = self.merge_sort(arr, mid+1, right)
        pl, pr = 0, 0
        for i in range(left, right+1):
            if pl == len(larr):
                arr[i] = rarr[pr]
                pr += 1
            elif pr == len(rarr):
                arr[i] = larr[pl]
                self.count[arr[i]] += pr
                pl += 1
            elif self.nums[larr[pl]] <= self.nums[rarr[pr]]:
                arr[i] = larr[pl]
                self.count[arr[i]] += pr
                pl += 1
            else:
                arr[i] = rarr[pr]
                pr += 1
        return arr[left:right+1]

 

3. AVL Tree

class TreeNode:
    def __init__(self, val, smaller):
        self.val = val
        self.freq = 1
        self.smaller = smaller
        self.left = None
        self.right = None
        self.height = 1

class AVL:
    def __init__(self):
        self.root = None

    def _height(self, node):
        if not node:
            return 0
        return node.height

    def _balance(self, node):
        if not node:
            return 0
        return self._height(node.left) - self._height(node.right)

    def _find_successor_node(self, node):
        while node.left:
            node = node.left
        return node

    def _rotateR(self, node):
        y = node.left
        node.smaller = node.smaller - y.smaller - y.freq
        t2 = y.right
        y.right = node
        node.left = t2
        node.height = 1 + max(self._height(node.left), self._height(node.right))
        y.height = 1 + max(self._height(y.left), self._height(y.right))
        return y

    def _rotateL(self, node):
        y = node.right
        y.smaller = y.smaller + node.smaller + node.freq
        t2 = y.left
        y.left = node
        node.right = t2
        node.height = 1 + max(self._height(node.left), self._height(node.right))
        y.height = 1 + max(self._height(y.left), self._height(y.right))
        return y

    def insert(self, val):
        self.root, smaller = self._insert(self.root, val, 0)
        return smaller

    def _insert(self, node, val, smaller):
        # Termination: Reaching Leaf
        if not node:
            return TreeNode(val, 0), smaller

        if val == node.val:
            node.freq += 1
            return node, node.smaller + smaller
        
        if val < node.val:
            node.smaller += 1
            node.left, smaller = self._insert(node.left, val, smaller)
        else:
            node.right, smaller = self._insert(node.right, val, smaller+node.smaller+node.freq)
        node.height = 1 + max(self._height(node.left), self._height(node.right))

        balance = self._balance(node)
        # LL Case -> Right Rotation of node
        if balance > 1 and val < node.left.val:
            return self._rotateR(node), smaller
        # RR Case -> Left Rotation of node
        if balance < -1 and val > node.right.val:
            return self._rotateL(node), smaller
        # LR Case -> Left Rotation of node.left -> Right Rotation of node
        if balance > 1 and val > node.left.val:
            node.left = self._rotateL(node.left)
            return self._rotateR(node), smaller
        # RL Case -> Right Rotation of node.right -> Left Rotation of node
        if balance < -1 and val < node.right.val:
            node.right = self._rotateR(node.right)
            return self._rotateL(node), smaller
        return node, smaller


class Solution:
    def countSmaller(self, nums):
        tree = AVL()
        ret = []
        for i in range(len(nums)-1, -1, -1):
            num = nums[i]
            ret.append(tree.insert(num))
        return ret[::-1]

 

4. Segment Tree

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        offset = 10**4
        n = 2 * 10**4 + 1
        
        def update(num, idx=1, l=0, r=n-1):
            if l == r:
                tree[idx] += 1
                return
            mid = (l + r) // 2
            if num <= mid:
                update(num, idx*2, l, mid)
            else:
                update(num, idx*2+1, mid+1, r)
            tree[idx] = tree[idx*2] + tree[idx*2+1]
        
        def query(low, high, idx=1, l=0, r=n-1):
            if l == low and high == r:
                return tree[idx]
            mid = (l + r) // 2
            if high <= mid:
                return query(low, high, idx*2, l, mid)
            elif low > mid:
                return query(low, high, idx*2+1, mid+1, r)
            return query(low, mid, idx*2, l, mid) + query(mid+1, high, idx*2+1, mid+1, r)

        tree = [0] * (4 * n)
        ret = [0] * len(nums)
    
        for i in range(len(nums)-1, -1, -1):
            num = nums[i] + offset
            update(num)
            ret[i] = query(0, num-1)
        return ret