NUHMAN.com

Introduction

LeetCode 315: Count of Smaller Numbers After Self asks us to count, for each element in a given array, how many elements to the right of it are smaller than it. This problem is a variation of the inversion count problem, where the goal is to efficiently count the number of elements that are smaller and appear after a given element.

The brute force approach would involve checking each element to the right for every element in the array, resulting in O(n²) time complexity. However, we can optimize this to O(n log n) using merge sort or binary search techniques.

Problem Statement

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

Input:

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

Output:

• answer = [2, 1, 1, 0]

Explanation:

For each number in the array, we want to count how many numbers to the right are smaller:

• 5 has 2 numbers smaller than it (2 and 1).
• 2 has 1 number smaller than it (1).
• 6 has 1 number smaller than it (1).
• 1 has no numbers smaller than it.

Step-by-Step Solution

🧠 Intuition

We can approach this problem efficiently using merge sort with a twist. While performing the merge step in merge sort, we can count how many smaller elements are present to the right of each element as we merge the two sorted halves.

This works because:

• When merging two sorted subarrays, if an element from the right subarray is smaller than an element from the left subarray, all the remaining elements in the left subarray are greater than the current element from the right subarray.
• By counting these comparisons during the merge step, we can accumulate the number of smaller elements to the right for each element.

✅ Approach

1. Merge Sort with Count:
2. Perform a merge sort on the array. During the merge step, when comparing elements from the left and right subarrays:

• If an element from the right subarray is smaller than an element from the left subarray, it means that element from the left subarray has as many smaller elements to its right as there are remaining elements in the right subarray.

1. Store the Counts:
2. Store the count of smaller elements for each index in a result array. For each merge, keep track of how many times an element from the left subarray has a smaller number in the right subarray.
3. Merge the Arrays:
4. After counting the smaller elements during the merge, merge the two subarrays as in a normal merge sort.

✅ Python Code

python

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        def merge_sort(nums, start, end, indices, counts):
            if start >= end:
                return
            mid = (start + end) // 2
            merge_sort(nums, start, mid, indices, counts)
            merge_sort(nums, mid + 1, end, indices, counts)
            merge(nums, start, mid, end, indices, counts)

        def merge(nums, start, mid, end, indices, counts):
            temp = []
            right_count = 0
            i, j = start, mid + 1
            while i <= mid and j <= end:
                if nums[indices[i]] <= nums[indices[j]]:
                    counts[indices[i]] += right_count
                    temp.append(indices[i])
                    i += 1
                else:
                    right_count += 1
                    temp.append(indices[j])
                    j += 1
            while i <= mid:
                counts[indices[i]] += right_count
                temp.append(indices[i])
                i += 1
            while j <= end:
                temp.append(indices[j])
                j += 1
            for i in range(start, end + 1):
                indices[i] = temp[i - start]

        n = len(nums)
        indices = list(range(n))
        counts = [0] * n
        merge_sort(nums, 0, n - 1, indices, counts)
        return counts

Explanation of the Code

1. Merge Sort with Counting:
2. The merge_sort function is the main recursive function that divides the array and processes each subarray. It takes nums, the starting and ending indices of the current subarray, an array indices which stores the original indices of the elements, and counts which will store the result.
3. Merge Step:
4. In the merge function:

• If an element from the left subarray is smaller than an element from the right subarray, we increment the count of the element from the left subarray by the number of remaining elements in the right subarray (right_count).
• We maintain an array temp to store the merged subarray.

1. Final Result:
2. After the merge sort is completed, counts will contain the count of smaller elements after each element in the original array.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n log n)Space ComplexityO(n)

• Time Complexity:
• The time complexity is O(n log n) because we are using a divide-and-conquer approach (merge sort) to split the array into smaller subarrays and then merge them back while counting the smaller elements. Each merge operation takes O(n) time, and the depth of recursion is O(log n).
• Space Complexity:
• The space complexity is O(n) due to the auxiliary arrays indices and counts that store the indices and the counts of smaller elements, respectively.

🔍 Edge Cases

1. Empty Array:
2. If the input array is empty, the result is an empty list, as there are no elements to process.
3. Array with All Identical Elements:
4. If the array contains identical elements, the result will be a list of zeros because no element is smaller than any other element.
5. Array with Decreasing Order:
6. If the array is sorted in strictly decreasing order, the result will be a list where each element is smaller than the previous one, resulting in a list of counts where each count is the number of elements after it.
7. Array with Increasing Order:
8. If the array is sorted in strictly increasing order, the result will be a list of zeros because there are no smaller elements after any element.

✅ Conclusion

LeetCode 315: Count of Smaller Numbers After Self is an algorithmic problem where we need to efficiently count how many elements to the right of each element are smaller. By using a modified merge sort approach, we can solve this problem in O(n log n) time, making it much more efficient than the brute force method.

This solution provides a clear example of how divide-and-conquer algorithms can be adapted to solve problems involving counting inversions or smaller elements in a sequence.