LeetCode Solutions Blog

Count of Smaller Numbers After Self

Number: 315

Difficulty: Hard

Paid? No

Problem Description

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

Key Insights

The brute force solution takes O(n²) time, which is too slow for large input arrays.
An efficient approach leverages the concept of Merge Sort to both sort the array and count the number of smaller elements by tracking the number of elements that "jump over" during the merge step.
Other efficient methods include Binary Indexed Trees (Fenwick Tree) or Balanced Binary Search Trees.

Space and Time Complexity

Time Complexity: O(n log n) on average due to the merge sort based approach. Space Complexity: O(n) for auxiliary arrays used during sorting and counting.

Solution

We use a modified Merge Sort to sort the array while counting the number of smaller elements to the right. We keep track of the original indices by pairing each element with its index. During the merge process, when an element from the left subarray is placed into the temporary array, we add the count of elements from the right subarray that have already been placed (since these represent smaller elements that were to its right). This efficient divide and conquer strategy guarantees an overall O(n log n) time complexity. Care must be taken to update the counts based on indices and during the merge step.

Code Solutions

# Python solution using merge sort approach

def countSmaller(nums):
    n = len(nums)
    # Initialize counts array for results
    counts = [0] * n
    # Pair each element with its original index
    enum = [(num, i) for i, num in enumerate(nums)]
    
    # Recursive function for merge sort with counting
    def mergeSort(arr):
        if len(arr) <= 1:
            return arr
        # Split the array into two halves
        mid = len(arr) // 2
        left = mergeSort(arr[:mid])
        right = mergeSort(arr[mid:])
        merged = []
        l = r = 0
        # r_count counts number of elements taken from right array
        r_count = 0
        while l < len(left) and r < len(right):
            # If left element is less or equal, it means current right elements are smaller
            if left[l][0] <= right[r][0]:
                # update count for original index
                counts[left[l][1]] += r_count
                merged.append(left[l])
                l += 1
            else:
                # right element is smaller, so increment r_count and add it to merged
                merged.append(right[r])
                r += 1
                r_count += 1
        # Append remaining elements from left reduce count by accumulated right elements
        while l < len(left):
            counts[left[l][1]] += r_count
            merged.append(left[l])
            l += 1
        # Append any remaining elements from right side
        while r < len(right):
            merged.append(right[r])
            r += 1
        return merged

    # Start the merge sort process
    mergeSort(enum)
    return counts

# Example test
print(countSmaller([5, 2, 6, 1]))  # Expected output: [2, 1, 1, 0]