Count Inversions

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.

Approach

1. 1Create 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.
2. 2Recursively 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.
3. 3Split 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.
4. 4Merge 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.
5. 5When 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].
6. 6Copy 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.
7. 7Copy 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.
8. 8Return 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

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

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

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

Common mistakesthree lines that change the counted relation