Skip to main content
Back to ChallengesCount Inversions in an ArrayHard 45 min

Count Inversions in an Array

Inversion Count for an array indicates how far the array is from being sorted. If the array is already sorted, then the inversion count is 0. If an array is sorted in the reverse order, then the inversion count is the maximum.

Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Examples

Input: arr = [2, 4, 1, 3, 5]
Output: 3
The inversions are (2,1), (4,1), and (4,3).

Constraints

  • • 1 <= arr.length <= 10^5
  • • 1 <= arr[i] <= 10^6

Complexity Analysis

Time
O(N log N)
modifies Merge Sort.
Space
O(N)
auxiliary arrays during merge.

Test Cases

#1 Standard case
Input: arr = [2,4,1,3,5]
Expected: 3
#2 Reversed array
Input: arr = [5,4,3,2,1]
Expected: 10
JavaScript
Output
Click "Run Code" to see output here...