Count Inversions — Editorial

Opening the reading…

Intuitioncounting many pairs from one sorted comparison

The direct definition checks every earlier position against every later position, but most of those comparisons do not need to be considered separately. Split the array into two parts and count inversions entirely inside the left part, entirely inside the right part, and across the split. The first two counts are smaller copies of the original problem.

After recursively sorting both halves, consider a right-half value a[j] that is smaller than the current left-half value a[i]. Because the left half is sorted, a[j] is also smaller than every remaining left-half value from i through mid - 1. One comparison therefore contributes mid - i inversions at once. Choosing a[i] when a[i] <= a[j] is important: equal values are not inversions, and keeping the left value first preserves that rule.

One right-half selection can account for all remaining larger values in the left half.

Approach

Create one temporary array and one 64-bit total, because every merge needs scratch space and the number of inversions can exceed the 32-bit range.

Recursively solve the half-open range [left, right), stopping when it contains zero or one element, because such a range cannot contain a pair and is already sorted.

Split at mid = left + (right - left) / 2 and count the left and right halves before merging, because those counts represent inversions whose two positions stay within one half.

Merge the two sorted halves with pointers i and j, taking a[i] whenever a[i] <= a[j], because equal values must not be counted and the left value is safe to place first.

When a[j] < a[i], add mid - i to the 64-bit total before copying a[j], because every unmerged left value is at least a[i] and therefore strictly greater than a[j].

Copy all leftover values from either half, because the main loop stops as soon as one side is exhausted and the merged range still has to contain every value.

Copy the temporary range back into the input array, because the parent merge relies on each child range being sorted; without this step, the batch-counting claim no longer holds.

Return the total from the full range, because the recursive totals and every cross-half batch together partition every inversion exactly once.

Complexitythe count is accumulated while sorting

MEASURE	BOUND	WHY
Time	O(n log n)	At each recursion depth, all ranges together scan and copy n values during their merges. There are O(log n) depths, and an inversion is counted only when its two values first lie in different child ranges, so no pair is counted twice.
Space	O(n) extra	The temporary array stores one value per input position, while the recursion stack uses O(log n) frames. The returned count is not output storage; the array itself is mutated in place, so the extra space is O(n), including the worst input shape.

Here n is the array length. The merge sort has logarithmic depth because each range is split in half.

Annotated solutionC++ · recursive merge sort · one reusable buffer

CPPCount within both children, count cross pairs during merge, then return the 64-bit total.

#include <vector>
using namespace std;

class Solution {
    long long mergeAndCount(vector<int>& a, vector<int>& temp, int left, int right) {
        if (right - left <= 1) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        long long answer = mergeAndCount(a, temp, left, mid);
        answer += mergeAndCount(a, temp, mid, right);

        int i = left;
        int j = mid;
        int k = left;

        while (i < mid && j < right) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                answer += static_cast<long long>(mid - i);
                temp[k++] = a[j++];
            }
        }

        while (i < mid) {
            temp[k++] = a[i++];
        }
        while (j < right) {
            temp[k++] = a[j++];
        }

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

        return answer;
    }

public:
    long long countInversions(vector<int> arr) {
        vector<int> temp(arr.size());
        return mergeAndCount(arr, temp, 0, static_cast<int>(arr.size()));
    }
};

The comparison uses <= rather than < for a precise reason: equal values must leave the left half first without adding to the answer. The other key line is answer += mid - i. By the time a right value wins, every left value before i has already been merged, while every left value from i onward is greater than that right value.

The frequency-tree alternativea reasonable option when the value range is small

Because each value is between 1 and 10000, you can process the array from right to left with a Fenwick tree. The tree stores how many values have already appeared to the right at each value, so querying values below arr[i] gives exactly the number of positions j with i < j and arr[i] > arr[j]. This is a different arrangement, not a strict improvement over merge sort here.

CPPFenwick tree alternative: query smaller values to the right before inserting the current value.

#include <vector>
using namespace std;

class Solution {
public:
    long long countInversions(vector<int> arr) {
        const int MAX_VALUE = 10000;
        vector<int> tree(MAX_VALUE + 1, 0);

        auto add = [&](int index) {
            while (index <= MAX_VALUE) {
                ++tree[index];
                index += index & -index;
            }
        };

        auto sum = [&](int index) {
            int total = 0;
            while (index > 0) {
                total += tree[index];
                index -= index & -index;
            }
            return total;
        };

        long long answer = 0;
        for (int i = static_cast<int>(arr.size()) - 1; i >= 0; --i) {
            answer += sum(arr[i] - 1);
            add(arr[i]);
        }
        return answer;
    }
};

With V as the largest possible value, this alternative takes O(n log V) time and O(V) extra space; here V is fixed by the value constraint. It avoids modifying the array and can be attractive when V is much smaller than n. Merge sort is more general because it does not need a bounded value range, while both approaches require 64-bit accumulation.