Count triplets which form an inversion in an array
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,
Output: The inversion count is 2
There are two inversions of size three in the array:
(9, 6, 4) and (9, 6, 5).
Input: A[] = [9, 4, 3, 5, 1]
Output: The inversion count is 5
There are five inversions of size three in the array:
(9, 4, 3), (9, 4, 1), (9, 3, 1), (4, 3, 1), and (9, 5, 1).
A naive solution is 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.
The implementation can be seen below in C, Java, and Python:
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 |
#include <stdio.h> // Function to find inversion count of size 3 in a given array int findInversionCount(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", findInversionCount(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 |
class Main { // Function to find inversion count of a given array public static int findInversionCount(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 " + findInversionCount(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 a given list def findInversionCount(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", findInversionCount(A)) |
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 array element, 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 the 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 |
#include <stdio.h> // Function to find inversion count of size 3 in a given array int findInversionCount(int arr[], int n) { int inversionCount = 0; // consider `arr[j]` as the middle element of a triplet, and find `arr[i]` and // `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", findInversionCount(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 a given array public static int findInversionCount(int[] arr) { int inversionCount = 0; // consider `arr[j]` as the middle element of a triplet, and find `arr[i]` // and `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 " + findInversionCount(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 a given list def findInversionCount(A): inversionCount = 0 # consider `A[j]` as the middle element of a triplet, and find `A[i]` and `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", findInversionCount(A)) |
Output:
The inversion count is 5
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)