Count of Smaller Numbers After Self

Problem: Count of Smaller Number After Self

We can use merge sort to solve this problem. While we are merging two lists, if we find i-th element in left list should be inserted just in front of j-th element in right list, it means that there are j-1 elements in right list are smaller than and right to i-th element in left list. There's another solution using binary indexed tree which is more tricky and complex.

Code in Python:

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [0] * len(nums)

        def mergeSort(numbers):
            half = len(numbers) / 2
            if half:
                left, right = mergeSort(numbers[:half]), mergeSort(numbers[half:])
                i, j, m, n = 0, 0, len(left), len(right)
                while i < m or j < n:
                    if j == n or i < m and left[i][1] <= right[j][1]:
                        res[left[i][0]] += j
                        numbers[i+j] = left[i]
                        i += 1
                    else:
                        numbers[i+j] = right[j]
                        j += 1
            return numbers

        mergeSort(list(enumerate(nums)))
        return res