Count of Smaller Numbers After Self

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].

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 1 smaller element (1). To the right of 1 there is 0 smaller element.

Example 2:

Input: nums = [-1] Output: [0]

Example 3:

Input: nums = [-1,-1] Output: [0,0]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Approach: Merge Sort with Index Tracking (Divide and Conquer)

Algorithm

1. Maintain an array of indices so the original positions are preserved
2. Perform merge sort on the values, but count how many elements from the right half move before an element of the left half
3. When an element from the right half is merged before a left element, every remaining element in the left half has one more smaller element to its right
4. Accumulate these counts into the result array at the original indices

Time & Space Complexity

• Time Complexity: O(n log n) - standard merge sort cost
• Space Complexity: O(n) - the temporary arrays used during merging

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class CountOfSmallerNumbersAfterSelf {

    private static int[] count;
    private static int[] index;

    /**
     * Count the number of smaller elements to the right of each element.
     * @param nums Input array
     * @return List of counts
     */
    public static List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        count = new int[n];
        index = new int[n];

        for (int i = 0; i < n; i++) {
            index[i] = i;
        }

        mergeSort(nums, new int[n], new int[n], 0, n - 1);

        List<Integer> result = new ArrayList<>();
        for (int c : count) {
            result.add(c);
        }
        return result;
    }

    private static void mergeSort(int[] nums, int[] tempNums, int[] tempIndex, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, tempNums, tempIndex, lo, mid);
        mergeSort(nums, tempNums, tempIndex, mid + 1, hi);

        for (int i = lo; i <= hi; i++) {
            tempNums[i] = nums[i];
            tempIndex[i] = index[i];
        }

        int i = lo;
        int j = mid + 1;
        int k = lo;
        int rightCount = 0;

        while (i <= mid && j <= hi) {
            if (tempNums[i] <= tempNums[j]) {
                count[tempIndex[i]] += rightCount;
                nums[k] = tempNums[i];
                index[k] = tempIndex[i];
                i++;
                k++;
            } else {
                rightCount++;
                nums[k] = tempNums[j];
                index[k] = tempIndex[j];
                j++;
                k++;
            }
        }

        while (i <= mid) {
            count[tempIndex[i]] += rightCount;
            nums[k] = tempNums[i];
            index[k] = tempIndex[i];
            i++;
            k++;
        }
        while (j <= hi) {
            nums[k] = tempNums[j];
            index[k] = tempIndex[j];
            j++;
            k++;
        }
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {5, 2, 6, 1};
        System.out.println("Input: nums = [5, 2, 6, 1]");
        System.out.println("Output: " + countSmaller(nums1));
        // Expected: [2, 1, 1, 0]

        int[] nums2 = {-1};
        System.out.println("Input: nums = [-1]");
        System.out.println("Output: " + countSmaller(nums2));
        // Expected: [0]

        int[] nums3 = {-1, -1};
        System.out.println("Input: nums = [-1, -1]");
        System.out.println("Output: " + countSmaller(nums3));
        // Expected: [0, 0]
    }
}

Example Walkthrough

For nums = [5, 2, 6, 1]:

1. Split into [5, 2] and [6, 1]
2. Merge [5] and [2]: 2 comes before 5, so count[0] += 1. Result [2, 5]
3. Merge [6] and [1]: 1 comes before 6, so count[2] += 1. Result [1, 6]
4. Merge [2, 5] and [1, 6]: 1 comes first (rightCount=1); then 2 -> count[1] += 1; then 5 -> count[0] += 1; then 6
5. Final counts: [2, 1, 1, 0]

Key Points

1. Inversion Counting: This is a classic inversion-counting variant applied to each element
2. Index Tracking: Merging values alone loses the original positions, so track indices
3. During Merge: When a right-half element is placed first, every remaining left element gains one smaller-right element
4. Stable Sort Property: Equal elements do not count as smaller, handled by using <= in the merge comparison
5. O(n log n): The divide and conquer approach improves on the naive O(n²) brute force