Count of Smaller Numbers After Self

Intuitionturning a right-side query into work done during merging

For nums[i], you need to count values to its right that are strictly smaller. Looking rightward separately for every index repeats the same comparisons and takes quadratic time. The useful change is to group indices into sorted ranges, where a whole block of values can be known to be smaller without checking its elements one by one.

Merge sort creates exactly the separation you need. During a merge, the left half contains earlier original indices and the right half contains later original indices. When a right-half value is moved before a left-half value, it is smaller than that left value and belongs to its right side. The number of right-half values already moved is therefore the count to add for that left element.

Approachsix steps that preserve value order and original positions

1. 1Store each value together with its original index, because sorting changes positions but counts must still be returned in the input order.
2. 2Run merge sort on these pairs by value, because each merge puts a later-index half beside an earlier-index half where whole groups can be counted at once.
3. 3Merge the sorted left and right halves with two pointers, because both halves are already sorted and the next smallest pair is always at one of those pointers.
4. 4When the right value is strictly smaller, copy it first and advance the right pointer, because it has now passed every remaining left value and increases their future smaller-right count.
5. 5When a left value is chosen, add j - mid - 1 to counts[arr[i].second], because exactly that many right-half values have already been copied before it; using <= keeps equal values from being counted as smaller.
6. 6Copy every leftover left value with the same accumulated count, then copy the leftover right values and write the merged range back, because later merges require this range to remain sorted.

Complexitythe input arrangement does not change the merge bound

Annotated solutionC++ · stable merge sort · counts written by original index

#include <vector>
#include <utility>

using namespace std;

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        vector<int> counts(n, 0);
        vector<pair<int, int>> arr(n);

        for (int i = 0; i < n; ++i) {
            arr[i] = {nums[i], i};
        }

        vector<pair<int, int>> temp(n);
        mergeSort(arr, 0, n - 1, temp, counts);
        return counts;
    }

private:
    void mergeSort(vector<pair<int, int>>& arr, int left, int right,
                   vector<pair<int, int>>& temp, vector<int>& counts) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid, temp, counts);
        mergeSort(arr, mid + 1, right, temp, counts);
        merge(arr, left, mid, right, temp, counts);
    }

    void merge(vector<pair<int, int>>& arr, int left, int mid, int right,
               vector<pair<int, int>>& temp, vector<int>& counts) {
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (arr[i].first <= arr[j].first) {
                temp[k] = arr[i];
                counts[arr[i].second] += j - mid - 1;
                ++i;
            } else {
                temp[k] = arr[j];
                ++j;
            }
            ++k;
        }

        while (i <= mid) {
            temp[k] = arr[i];
            counts[arr[i].second] += j - mid - 1;
            ++i;
            ++k;
        }

        while (j <= right) {
            temp[k] = arr[j];
            ++j;
            ++k;
        }

        for (int p = left; p <= right; ++p) {
            arr[p] = temp[p];
        }
    }
};

The pair's second field is the key that prevents sorting from losing the answer's position. The merge count is added before that pair moves on, and the same count is added to leftover left pairs because every remaining right pair has already been moved before them. The <= comparison is deliberate: an equal right value is not smaller, so it must stay in the right half's count of moved values.

The Fenwick tree alternativea direct right-to-left query with the same asymptotic cost

A Fenwick tree gives a different arrangement of the same idea. Coordinate-compress the values into ranks, walk nums from right to left, and let the tree store how many processed values have each rank. The prefix sum before the current rank is exactly the number of strictly smaller values already seen, which are precisely the values to the right.

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> values = nums;
        sort(values.begin(), values.end());
        values.erase(unique(values.begin(), values.end()), values.end());

        int m = static_cast<int>(values.size());
        vector<int> tree(m + 1, 0);
        vector<int> counts(nums.size(), 0);

        for (int i = static_cast<int>(nums.size()) - 1; i >= 0; --i) {
            int rank = static_cast<int>(
                lower_bound(values.begin(), values.end(), nums[i]) - values.begin()
            ) + 1;

            counts[i] = query(tree, rank - 1);
            add(tree, rank, 1);
        }

        return counts;
    }

private:
    void add(vector<int>& tree, int index, int amount) {
        while (index < static_cast<int>(tree.size())) {
            tree[index] += amount;
            index += index & -index;
        }
    }

    int query(const vector<int>& tree, int index) {
        int total = 0;
        while (index > 0) {
            total += tree[index];
            index -= index & -index;
        }
        return total;
    }
};

This is not an asymptotic optimisation: coordinate compression takes O(n log n), and each query and update takes O(log n), so the total remains O(n log n) with O(n) extra space. It buys a direct expression of the question, while merge sort avoids a separate rank structure and naturally explains the inversion count. Choose the tree when point updates and prefix queries already fit your toolkit.

Common mistakesthree lines that quietly change the meaning of smaller