We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count of Smaller Numbers After Self

Difficulty: Hard

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 problem requires counting the number of smaller elements to the right for each element in the array.
  • A naive approach with nested loops would result in O(n^2) time complexity, which is inefficient for large arrays.
  • Efficient approaches involve data structures like Binary Indexed Trees, Segment Trees, or utilizing a modified Merge Sort algorithm to achieve O(n log n) time complexity.

Space and Time Complexity

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

Solution

To solve this problem, we can utilize a modified Merge Sort algorithm. The idea is to divide the array into smaller subarrays and count how many elements from the right subarray are smaller than the elements in the left subarray during the merge process. This allows us to count the smaller numbers efficiently.

  1. Implement a recursive merge sort function that will split the array and count smaller elements.
  2. During the merge step, maintain a count of how many elements from the right subarray are less than the current element from the left subarray.
  3. Store the results in an auxiliary array, which will eventually yield the final counts.

Code Solutions

def countSmaller(nums):
    def merge_sort(enum):
        if len(enum) <= 1:
            return enum, []
        mid = len(enum) // 2
        left, left_counts = merge_sort(enum[:mid])
        right, right_counts = merge_sort(enum[mid:])
        
        counts = [0] * len(enum)
        j = 0
        for i in range(len(left)):
            while j < len(right) and right[j][0] < left[i][0]:
                j += 1
            counts[left[i][1]] += j
        
        merged = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i][0] <= right[j][0]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        
        return merged, counts

    indexed_nums = list(enumerate(nums))
    _, counts = merge_sort(indexed_nums)
    return counts
← Back to All Questions