Given an array, count the total number of triplets, which leads to an inversion. If (i < j < k) and (A[i] > A[j] > A[k]), then we can say that triplet (i, j, k) formed an inversion in an array A.
For example,
A Brute-force solution would be to consider each triplet (A[i], A[j], A[k]) in array A by looping through all possible value of i, j and k. If the inversion condition is satisfied by a triplet, then increment the inversion count. The time complexity of this solution is O(n3), where n is the size of the input.
C
|
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
|
#include <stdio.h>
// Function to find inversion count of size 3 in a given array
int getInversionCount(int arr[], int n)
{
int inversionCount = 0;
for (int i = 0; i < n – 2; i++)
{
for (int j = i + 1; j < n – 1; j++)
{
for (int k = j + 1; k < n; k++)
{
if (arr[i] > arr[j] && arr[j] > arr[k])
{
inversionCount++;
}
}
}
}
return inversionCount;
}
int main(void)
{
int arr[] = { 9, 4, 3, 5, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
printf(“The inversion count is %d”, getInversionCount(arr, n));
return 0;
}
|
Output:
The inversion count is 5
Java
|
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
|
class Main
{
// Function to find inversion count of the given array
public static int getInversionCount(int[] arr) {
int inversionCount = 0;
for (int i = 0; i < arr.length – 2; i++) {
for (int j = i + 1; j < arr.length – 1; j++) {
for (int k = j + 1; k < arr.length; k++) {
if (arr[i] > arr[j] && arr[j] > arr[k]) {
inversionCount++;
}
}
}
}
return inversionCount;
}
public static void main(String[] args) {
int[] arr = { 9, 4, 3, 5, 1 };
System.out.println(“The inversion count is “ + getInversionCount(arr));
}
}
|
Output:
The inversion count is 5
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
# Function to find inversion count of the given list
def getInversionCount(A):
inversionCount = 0
for i in range(len(A) – 2):
for j in range(i + 1, len(A) – 1):
for k in range(j + 1, len(A)):
if A[i] > A[j] > A[k]:
inversionCount = inversionCount + 1
return inversionCount
if __name__ == ‘__main__’:
A = [9, 4, 3, 5, 1]
print(“Inversion count is”, getInversionCount(A))
|
Output:
The inversion count is 5
Download Run Code
Output:
The inversion count is 5
Download Run Code
Output:
The inversion count is 5
Download Run Code
Output:
The inversion count is 5
We can easily reduce the time complexity of the solution from O(n3) to O(n2). The idea is to consider each element in array arr[j] as the middle element of the triplet. Then the total number of inversions with arr[j] as the middle element is the product of the total number of elements greater than arr[j] with index less than j with the total number of elements smaller than arr[j] with index more than j.
Basically, for each element of the array, we count all elements more than it to its left and all elements less than it to its right and add their product to the result. Following is C, Java, and Python program that demonstrates it:
C
|
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
|
#include <stdio.h>
// Function to find inversion count of size 3 in a given array
int getInversionCount(int arr[], int n)
{
int inversionCount = 0;
// consider `arr[j]` as the middle element of the triplet and find `arr[i]` &
// `arr[k]` such that `(arr[i], arr[j], arr[k])` form an inversion
for (int j = 1; j < n – 1; j++)
{
// count number of elements greater than `arr[j]` in the `range[0,j-1]`
int greater = 0;
for (int i = 0; i < j; i++)
{
if (arr[i] > arr[j])
{
greater++;
}
}
// count number of elements smaller than `arr[j]` in range `[j+1,n-1]`
int smaller = 0;
for (int k = j + 1; k < n; k++)
{
if (arr[k] < arr[j])
{
smaller++;
}
}
// the total number of inversions with `arr[j]` as the middle element
// is `greater × smaller`
inversionCount += (greater * smaller);
}
return inversionCount;
}
int main(void)
{
int arr[] = { 9, 4, 3, 5, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
printf(“The inversion count is %d”, getInversionCount(arr, n));
return 0;
}
|
Output:
The inversion count is 5
Java
|
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
|
class Main
{
// Function to find inversion count of the given array
public static int getInversionCount(int[] arr) {
int inversionCount = 0;
// consider `arr[j]` as the middle element of the triplet and find `arr[i]` &
// `arr[k]` such that `(arr[i], arr[j], arr[k])` form an inversion
for (int j = 1; j < arr.length – 1; j++)
{
// count number of elements greater than `arr[j]` in the `range[0,j-1]`
int greater = 0;
for (int i = 0; i < j; i++)
{
if (arr[i] > arr[j])
{
greater++;
}
}
// count number of elements smaller than `arr[j]` in range `[j+1,n-1]`
int smaller = 0;
for (int k = j + 1; k < arr.length; k++)
{
if (arr[k] < arr[j])
{
smaller++;
}
}
// the total number of inversions with `arr[j]` as the middle element
// is `greater × smaller`
inversionCount += (greater * smaller);
}
return inversionCount;
}
public static void main(String[] args) {
int[] arr = { 9, 4, 3, 5, 1 };
System.out.println(“The inversion count is “ + getInversionCount(arr));
}
}
|
Output:
The inversion count is 5
Python
|
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
|
# Function to find inversion count of the given list
def getInversionCount(A):
inversionCount = 0
# consider `A[j]` as middle element of the triplet and find `A[i]` & `A[k]`
# such that `(A[i], A[j], A[k])` form an inversion
for j in range(1, len(A) – 1):
# count number of elements greater than `A[j]` in the `range[0,j-1]`
greater = 0
for i in range(j):
if A[i] > A[j]:
greater = greater + 1
# count the total number of elements smaller than `A[j]` in range `[j+1,n-1]`
smaller = 0
for k in range(j + 1, len(A)):
if A[k] < A[j]:
smaller = smaller + 1
# the total number of inversions with `A[j]` as the middle element
# is `greater × smaller`
inversionCount += (greater * smaller)
return inversionCount
if __name__ == ‘__main__’:
A = [9, 4, 3, 5, 1]
print(“Inversion count is”, getInversionCount(A))
|
Output:
The inversion count is 5
Download Run Code
Output:
The inversion count is 5
Download Run Code
Output:
The inversion count is 5