Count of Smaller Numbers After Self

Problem Statement

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

Example

Input:  nums = [5,2,6,1]
Output: [2,1,1,0]

Approach (Binary Search Insertion)

Scan from right to left, keeping a sorted list of the elements already seen. For each value, the number of smaller elements to its right equals its lower-bound insertion index in that list, which binary search finds in O(log n). Then insert the value.

Honest note: list insertion costs O(n), so this is O(n²) worst case. For the optimal O(n log n), use a Fenwick (BIT) tree or merge sort — both still rely on counting smaller elements.

Complexity

• Time: O(n log n) comparisons, O(n²) worst case due to list insertion
• Space: O(n)

Solution Code

Python

import bisect
def countSmaller(nums):
    seen = []
    res = [0] * len(nums)
    for i in range(len(nums) - 1, -1, -1):
        pos = bisect.bisect_left(seen, nums[i])
        res[i] = pos
        seen.insert(pos, nums[i])
    return res

Java

List<Integer> countSmaller(int[] nums) {
    List<Integer> seen = new ArrayList<>();
    Integer[] res = new Integer[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        int lo = 0, hi = seen.size();
        while (lo < hi) {                 // lower bound
            int mid = (lo + hi) / 2;
            if (seen.get(mid) < nums[i]) lo = mid + 1;
            else hi = mid;
        }
        res[i] = lo;
        seen.add(lo, nums[i]);
    }
    return Arrays.asList(res);
}

C++

vector<int> countSmaller(vector<int>& nums) {
    vector<int> seen, res(nums.size());
    for (int i = (int)nums.size() - 1; i >= 0; i--) {
        int pos = lower_bound(seen.begin(), seen.end(), nums[i]) - seen.begin();
        res[i] = pos;
        seen.insert(seen.begin() + pos, nums[i]);
    }
    return res;
}

Key Takeaways

• The count of smaller elements is just the lower-bound insertion index.
• Binary search gives the count in O(log n); insertion is the costly part.
• Reference: LeetCode 315; optimal via Fenwick tree / merge sort (CLRS Ch. 12-14).