Count Inversions
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
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;}