315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Solution: Merge Sort

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

        def merge_sort(indices):
            if len(indices) < 2:
                return indices
            half = len(indices) / 2
            left = merge_sort(indices[:half])
            right = merge_sort(indices[half:])
            return merge(left, right, indices)

        def merge(left, right, indices):
            for idx in xrange(len(indices) - 1, -1, -1):
                if not right or (left and nums[left[-1]] > nums[right[-1]]):
                    count[left[-1]] += len(right)  # key solution
                    indices[idx] = left.pop()
                else:
                    indices[idx] = right.pop()
            return indices

        merge_sort(range(len(nums)))
        return count

Lessons:

• Update counts during merge.