[LeetCode] 315. Count of Smaller Numbers After Self

 Problem : https://leetcode.com/problems/count-of-smaller-numbers-after-self/

The original array is unsorted. Iterate the input array from the rear and use insert sort to create a sorted sequence.  The insert position indicates the number of smaller elements.

Time Complexity = O ( N * Log N  + N * N ).   Inserting number to array is O(N) time complexity operation.

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]: 
        def lowerBound(n, dp):
            """
            the first poistion on the left where dp[i] <= n
            """
            left, right = 0, len(dp)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if dp[mid] == n:
                    right = mid
                elif dp[mid] < n:
                    left = mid + 1
                elif dp[mid] > n:
                    right = mid
            
            return right
        
        result = [0] * len(nums)
        dp = []
        
        for i in reversed(range(len(nums))):
            n = nums[i]
            # insert sort
            j = lowerBound(n, dp)
            dp.insert(j, n)
            
            result[i] = j
            
        return result

Use Python build-in lib:

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        dp = []
        result = [0] * len(nums)
        
        for i in reversed(range(len(nums))):
            
            lowerBound = bisect.bisect_left(dp, nums[i])
            
            result[i] = lowerBound
            
            bisect.insort_left(dp, nums[i])
        
        return result

Use segment tree:

class SegmentTree:
    def __init__(self, m):
        # M = number of leafs of the segement tree
        self.M = m
        
        # Because segement tree is a completed binary tree.
        # If number of leafs = M, then number of internal nodes = M - 1.
        # Because tree[0] will not be used, the total number of nodes = 2 * M
        self.tree = [0] * (2 * self.M)
        
    def update(self, n, delta):
        """
        update counter of number on index n
        """
        
        # number n leaf node index = n + M
        n += self.M
        self.tree[n] += delta
        
        n //= 2
        while n > 0:
            # left child node index = 2 * n
            # right child node index = 2 * n
            self.tree[n] = self.tree[2*n] + self.tree[2*n+1]
            n //= 2
    
    def query(self, left, right):
        """
        query accumulative count between range [left, right).
        the 'right' is excluded.
        """
        
        result = 0
        
        left += self.M
        right += self.M
        
        while left < right:
            if left & 1 == 1:
                # on left side, the left child node is not in the needed range.
                result += self.tree[left]
                left += 1
            
            left //= 2
            
            if right & 1 == 1:
                # on right side, the right child node is not in the needed range
                right -= 1
                result += self.tree[right]
            
            right //= 2
        
        return result

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        mi = min(nums)
        mx = max(nums) + 1
        m = mx - mi + 1
        segmentTree = SegmentTree(m)
        
        # query in segement tree for number of smaller elements to the right of nums[i]
        result = [0] * len(nums)
        for i in reversed(range(len(nums))):
            n = nums[i] - mi
            
            result[i] = segmentTree.query(0, n)
            segmentTree.update(n, 1)
        
        return result

Use fenwick tree:

class FenwickTree:
    def __init__(self, m):
        self.tree = [0] * m
    
    def update(self, n, delta):
        while n < len(self.tree):
            self.tree[n] += delta
            n += self.lowbit(n)
    
    def query(self, n):
        result = 0
        
        while n > 0 :
            result += self.tree[n]
            n -= self.lowbit(n)
        
        return result
            
    
    def lowbit(self, n):
        return n & (~(n-1))
        
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        mi = min(nums)
        mx = max(nums) + 1
        m = mx - mi + 1
        
        fenwickTree = FenwickTree(m)
        
        result = [0] * len(nums)
        
        for i in reversed(range(len(nums))):
            # fenwick tree node index starts with 1
            n = nums[i] - mi + 1
            
            result[i] = fenwickTree.query(n-1)
            fenwickTree.update(n, 1)
        
        return result

Use merge sort approach.

Split the nums array into left and right parts.

Sort the right part first, then for each number on the left part, use binary-search to find count of number less than it. (lower-bound)

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        result = [0] * len(nums)
        
        def mergeSort(left, right):
            if left + 1 == right: 
                return 

            mid = left + (right - left) // 2

            # sort right side
            mergeSort(mid, right)

            # for each number on left side, find
            # how many number is smaller than it on right side.
            for i in range(left, mid):
                lowerBound = bisect.bisect_left(nums, nums[i], mid, right)
                # count of smaller numbers = lowerBound - mid
                result[i] += lowerBound - mid
            
            # sort left side
            mergeSort(left, mid)
            
            # merge the sorted left and right side
            tmp = []
            i = left
            j = mid

            while i < mid and j < right:
                if nums[i] < nums[j]:
                    tmp.append(nums[i])
                    i += 1
                else:
                    tmp.append(nums[j])
                    j += 1

            while i < mid:
                tmp.append(nums[i])
                i += 1

            while j < right:
                tmp.append(nums[j])
                j += 1

            for i in range(right - left):
                nums[left+i] = tmp[i]
        
        # merge sort starts
        mergeSort(0, len(nums))
        
        return result