Problem Description
Inversion Count for an array indicates – how far (or close) the array is from being sorted. If the array is already sorted, then the inversion count is 0, but if the array is sorted in the reverse order, the inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j Count Inversions in an array
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.*;
class Program {
public int countInversions(int[] array) {
if(array.length <= 1) return 0;
return solve(array, 0, array.length-1);
}
public int solve(int[] a, int s, int e){
if(s==e) return 0;
int m = (e+s)/2;
int l = solve(a, s, m);
int r = solve(a, m+1,e);
return l+r+merge(a, s, m, e);
}
public int merge(int[] arr, int s, int m, int e){
int[] temp = new int[e-s+1];
int i=s;
int j=m+1;
int idx=0;
int count=0;
while(i<=m && j<=e){
if(arr[i] <= arr[j]){
temp[idx] = arr[i];
i++;
}else{
temp[idx] = arr[j];
j++;
count+=(m-i+1);
}
idx++;
}
for(int x=i; x<=m; x++){
temp[idx] = arr[x];
idx++;
}
for(int x=j; x<=e; x++){
temp[idx] = arr[x];
idx++;
}
for(int w=s; w<=e; w++){
arr[w] = temp[w-s];
}
return count;
}
}