Count of Smaller Numbers After Self — Editorial

Opening the reading…

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

Store each value together with its original index, because sorting changes positions but counts must still be returned in the input order.

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

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

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

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

Copy 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

MEASURE	BOUND	WHY
Time	O(n log n)	There are log n levels of splitting, and each level copies every pair in the active ranges once during merging. The two pointers only move forward within their ranges, so no element is scanned repeatedly at one level; the worst value arrangement has the same bound.
Space	O(n) extra	The pair array, temporary merge array, and counts array use linear storage; the returned counts array is required output and is excluded from the extra-space bound. The recursion adds O(log n) stack space, so the O(n) working arrays dominate, with no worse input shape because merge sort always splits by index.

Here n is the length of nums.

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

CPPMerge sort counts right-half values already moved before each left-half value.

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

CPPFenwick tree alternative: query ranks smaller than the current value while scanning from right to left.

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