DSA

Count Inversions

Covers: Brute Force, Merge Sort (Optimal).

August 8, 2026

Given an integer array nums, return the number of inversions in the array.

Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

A sorted array has an inversion count of 0.
An array sorted in descending order has the maximum number of inversions.
It indicates how far an array is from being sorted.

Approach 1: Brute Force#

Check every pair (i, j) where i < j and count pairs where nums[i] > nums[j]. The outer loop fixes the left element and the inner loop scans every element to its right — if the right element is smaller, it forms an inversion. This is correct but examines all O(n²) pairs, making it impractical for large inputs.

cpp

long long int numberOfInversions(vector<int> nums) {
    long long int inv = 0;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] > nums[j])
                inv++;
        }
    }
    return inv;
}

TC: O(n²)
SC: O(1)

Approach 2: Merge Sort (Optimal)#

Piggyback on merge sort — during the merge step, whenever an element from the right half is placed before an element from the left half, all remaining elements in the left half form inversions with it.

Key insight: When merging two sorted halves and left[i] > right[j], then every element from left[i] to the end of the left half is also greater than right[j] (since left half is sorted). So we add mid - i + 1 inversions in one shot.

cpp

long long int mergeCount(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp;
    int i = left, j = mid + 1;
    long long int count = 0;

    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp.push_back(nums[i++]);
        } else {
            // nums[i..mid] are all > nums[j]
            count += (mid - i + 1);
            temp.push_back(nums[j++]);
        }
    }
    while (i <= mid) temp.push_back(nums[i++]);
    while (j <= right) temp.push_back(nums[j++]);

    for (int k = left; k <= right; k++)
        nums[k] = temp[k - left];

    return count;
}

long long int mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return 0;
    int mid = (left + right) / 2;
    long long int count = 0;
    count += mergeSort(nums, left, mid);
    count += mergeSort(nums, mid + 1, right);
    count += mergeCount(nums, left, mid, right);
    return count;
}

long long int numberOfInversions(vector<int> nums) {
    return mergeSort(nums, 0, nums.size() - 1);
}

Walkthrough example: [3, 2, 1]

mergeSort([3,2,1])
  mergeSort([3,2])
    mergeSort([3]) → 0
    mergeSort([2]) → 0
    merge([3],[2]): 3 > 2 → count += 1, result [2,3]
  mergeSort([1]) → 0
  merge([2,3],[1]): 2 > 1 → count += 2, 3 > 1 already counted → result [1,2,3]

Total = 0 + 0 + 1 + 0 + 2 = 3 ✓

TC: O(n log n)
SC: O(n) — temp array during merge

Comparison#

Approach	TC	SC	Notes
Brute force	O(n²)	O(1)	Fine for n ≤ 1000
Merge sort	O(n log n)	O(n)	Optimal; counts during sort itself

DSAMajority Element IIExtended Boyer-Moore Voting — find all elements appearing more than ⌊n/3⌋ times. Time O(n), Space O(1).DSARemove Duplicates from Sorted Array IIKeep each unique element at most twice in-place. Optimal — Time O(n), Space O(1).DSARotate ArrayCovers: Brute Force, Extra Array, Optimal (Reverse). Optimal — Time O(n), Space O(1).

Approach 1: Brute Force#

Approach 2: Merge Sort (Optimal)#

Comparison#

Related articles