Count Inversions

Medium

Problem

An inversion is a pair of indices i < j with arr[i] > arr[j]. It measures how far the array is from sorted. Return the number of inversions.

Example 1

Input:  [2, 4, 1, 3, 5]
Output: 3

The inversions are (2,1), (4,1) and (4,3).

Also asked as: Count Inversion · Findthe inversion count

Test cases

Case 1

Input:    [2,4,1,3,5]
Expected: 3

Case 2

Input:    [5,4,3,2,1]
Expected: 10

Case 3

Input:    [1,2,3]
Expected: 0

Case 4

Input:    [1]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Merge sort

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

While merging two sorted halves, every time an element from the right half is picked before elements remain in the left, those remaining left elements are all inversions.

function countInversions(a) {
let count = 0;
const sort = (arr) => {
if (arr.length < 2) return arr;
const mid = arr.length >> 1;
const L = sort(arr.slice(0, mid));
const R = sort(arr.slice(mid));
const merged = [];
let i = 0, j = 0;
while (i < L.length && j < R.length) {
if (L[i] <= R[j]) merged.push(L[i++]);
else { merged.push(R[j++]); count += L.length - i; }
}
return merged.concat(L.slice(i), R.slice(j));
};
sort(a.slice());
return count;
}