Count Of Smaller Numbers After Self - Leetcode Solution

The Count of Smaller Numbers After Self problem on LeetCode is a challenging problem that requires you to find the number of elements that are smaller than the current element in an array. In this article, we will provide you with a detailed solution to this problem.

Problem Statement

Given an integer array nums, return an array answer such that answer[i] is the number of smaller elements to the right of nums[i].

Example 1: Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: 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 only 1 smaller element (1). To the right of 1 there is 0 smaller elements.

Approach

We will use the merge-sort approach to find the answer to this problem. The idea behind the merge-sort approach is to divide the array into two halves and count the number of smaller elements in each half separately. Once we have the counts from the left and right half, we merge the two arrays while keeping the order of the elements and updating the count of smaller elements.

Algorithm

1. Create an array res that will store the count of smaller elements for each element in nums.
2. Create a list of tuples index_num that will store the index and number pairs as (index, num) for each element in nums.
3. Create an empty list of tuples temp to store the temporary result.
4. Implement a merge-sort algorithm that sorts index_num and tracks the number of elements smaller than the current element in the right half.
5. For each element (index, num) in index_num, add the count of elements in the right half to res[index].

Python Implementation

Here's the Python implementation of the above algorithm:

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        res = [0]*len(nums)
        index_num = [(i, nums[i]) for i in range(len(nums))]
        temp = [0]*len(nums)
        
        def merge_sort(nums, left, right):
            if right - left <= 1:
                return nums[left:right]
            mid = (left + right)//2
            left_arr = merge_sort(nums, left, mid)
            right_arr = merge_sort(nums, mid, right)
            i, j = 0, 0
            count = 0
            while i < len(left_arr) or j < len(right_arr):
                if j == len(right_arr) or (i < len(left_arr) and left_arr[i][1] <= right_arr[j][1]):
                    temp[i + j] = left_arr[i]
                    res[left_arr[i][0]] += count
                    i += 1
                else:
                    temp[i + j] = right_arr[j]
                    count += 1
                    j += 1
            return temp[:i+j]
        
        merge_sort(index_num, 0, len(index_num))
        return res

Time Complexity: O(n log n) Space Complexity: O(n)

Let's understand the implementation step by step.

1. We create an empty list res that will store the count of smaller elements for each element in nums.

res = [0]*len(nums)

2. We create a list of tuples index_num that will store the index and number pairs as (index, num) for each element in nums.

index_num = [(i, nums[i]) for i in range(len(nums))]

3. We create an empty list of tuples temp to store the temporary result.

temp = [0]*len(nums)

4. We implement a merge-sort algorithm to sort index_num and count the number of elements smaller than the current element in the right half.

def merge_sort(nums, left, right):
    if right - left <= 1:
        return nums[left:right]
    mid = (left + right)//2
    left_arr = merge_sort(nums, left, mid)
    right_arr = merge_sort(nums, mid, right)
    i, j = 0, 0
    count = 0
    while i < len(left_arr) or j < len(right_arr):
        if j == len(right_arr) or (i < len(left_arr) and left_arr[i][1] <= right_arr[j][1]):
            temp[i + j] = left_arr[i]
            res[left_arr[i][0]] += count
            i += 1
        else:
            temp[i + j] = right_arr[j]
            count += 1
            j += 1
    return temp[:i+j]

merge_sort(index_num, 0, len(index_num))

5. For each element (index, num) in index_num, we add the count of elements in the right half to res[index].

for i, num in index_num:
    res[i] = res[i] + (len(nums) - 1) - i

6. Finally, we return res.

return res

Conclusion

In this article, we provided a detailed solution to the Count of Smaller Numbers After Self problem on LeetCode. We used the merge-sort approach to divide the array into two halves and count the number of smaller elements in each half separately. Finally, we merged the two arrays while keeping the order of the elements and updating the count of smaller elements. This problem can be solved in O(n log n) time complexity and O(n) space complexity.

1