Count Inversions Solutions & Complexity

1. Define the problem

Count Inversions

Given an integer array nums, count the number of inversions — pairs of indices i < j where nums_i > nums_j. A brute-force check of every pair takes O(n²) time. Instead, count inversions while merge sorting : whenever the merge step takes a value from the right run before the left run is empty, every value still waiting in the left run is out of order with it — add that whole count at once.

Constraints

0 ≤ nums.length ≤ 1000
-10⁴ ≤ nums_i ≤ 10⁴

Example

Inputnums = [8, 4, 2, 1]

Output6

Explanation Every pair is out of order: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) — 6 inversions total.

2. Know the words first

In plain terms

Inversion: A pair of positions where the earlier value is larger than the later one — a sign of how far the array is from sorted order.

3. Visualize the solution

Count inversions while merging sorted runs

Statussplit

Split [8, 4, 2, 1] into [8, 4] and [2, 1].

What happens in this step

arr = [8, 4, 2, 1]
mid = floor(4 / 2) = 2

left  = [8, 4]
right = [2, 1]

Neither half is trivially sorted (length > 1), so both recurse further, each accumulating their own inversion count first.

Step 1 of 5

Steps to visualize

Split the array in half recursively until each piece has one element.
Merge each pair of sorted pieces with two pointers, same as any merge sort.
Whenever the merge takes the right piece's value before the left piece is exhausted, every remaining left value forms an inversion with it — add that count all at once.
Add up the inversions found while merging at every level of the recursion.
The running total once the whole array is merged is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Count inversions while merging sorted runs

Statussplit

Split [8, 4, 2, 1] into [8, 4] and [2, 1].

What happens in this step

arr = [8, 4, 2, 1]
mid = floor(4 / 2) = 2

left  = [8, 4]
right = [2, 1]

Neither half is trivially sorted (length > 1), so both recurse further, each accumulating their own inversion count first.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function countInversions(nums) {
  function mergeCount(arr) {
    if (arr.length <= 1) return { sorted: arr, count: 0 };

    const mid = Math.floor(arr.length / 2);
    const leftResult = mergeCount(arr.slice(0, mid));
    const rightResult = mergeCount(arr.slice(mid));
    const left = leftResult.sorted;
    const right = rightResult.sorted;

    const sorted = [];
    let i = 0;
    let j = 0;
    let count = leftResult.count + rightResult.count;

    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        sorted.push(left[i]);
        i++;
      } else {
        // left[i..end] are all greater than right[j] — that many inversions, all at once
        count += left.length - i;
        sorted.push(right[j]);
        j++;
      }
    }

    while (i < left.length) sorted.push(left[i++]);
    while (j < right.length) sorted.push(right[j++]);

    return { sorted, count };
  }

  return mergeCount(nums).count;
}

Time: O(n log n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [8, 4, 2, 1]`	`6`	example from the docstring
`nums = []`	`0`	empty array
`nums = [5]`	`0`	smallest valid input, a single element
`nums = [1, 2, 3, 4]`	`0`	already sorted, no inversions
`nums = [1, 3, 2]`	`1`	exactly one out-of-order pair
`nums = [2, 2, 2]`	`0`	equal values are never inversions
`nums = [2, 1]`	`1`	boundary case, exactly two elements
`nums = [5, 4, 3, 2, 1]`	`10`	fully descending input, maximum possible inversions

Count Inversions