315.Count of Smaller Numbers After Self

Tags: [sort], [merge_sort], [trick]

Com: {g}

Link: https://leetcode.com/problems/count-of-smaller-numbers-after-self/\#/description

You are given an integer arraynumsand you have to return a newcountsarray. Thecountsarray has the property wherecounts[i]is the number of smaller elements to the right ofnums[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, Trick

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []

        elems = [(x, i) for i, x in enumerate(nums)]
        result = [0 for _ in xrange(len(nums))]
        self.merge_sort(elems, result)
        return result

    def merge_sort(self, elems, result):
        # base case
        if not elems or len(elems) == 1:
            return elems

        size = len(elems)
        left = self.merge_sort(elems[:size / 2], result)
        right = self.merge_sort(elems[size / 2:], result)

        right_counter = 0
        l = 0
        r = 0
        buff = []
        while l < len(left) and r < len(right):
            if left[l] <= right[r]:
                buff.append(left[l])
                result[left[l][1]] += right_counter
                l += 1
            else:
                buff.append(right[r])
                right_counter += 1
                r += 1

        while l < len(left):
            buff.append(left[l])
            result[left[l][1]] += right_counter
            l += 1
        while r < len(right):
            buff.append(right[r])
            r += 1

        return buff

Revelation:

• 'right_counter' here means: the number of right elements have been put on the left side.

Note:

• Time complexity = O(nlgn), n is the number of elements in the given array.