Count triplets which form an inversion in an array

Problem

Given an array, you need to count all inversion triplets. Inversion triplets are such that i<j<k and arr[i]>arr[j]>arr[k] , for some indices i , j , and k .

Sample Input

[1, 2, 4, 3, 2]

Sample Output

1

Brute Force Approach

You can consider every triplet present in the array and check the condition mentioned in the problem statement. This approach takes O(N3) time and is inefficient. Let’s look at a more efficient approach to solve this problem.

Efficient Approach

If we consider each element as the middle element one by one, we can iterate to the left and right side of this index and see which elements satisfy the given condition. The number of triplets formed using this element as middle of the triplet are: number of greater elements to the left * number of smaller elements to the right. The time complexity of this approach is O(N2).

C

#include <stdio.h>
 
int solve(int arr[], int n)
{
    int ans = 0;
     for (int j = 1; j < n - 1; j++)
    {
        int larger = 0;
        for (int i = 0; i < j; i++)
        {
            if (arr[i] > arr[j]) {
                larger++;
            }
        }
 
        int smaller = 0;
        for (int k = j + 1; k < n; k++)
        {
            if (arr[k] < arr[j]) {
                smaller++;
            }
        }
 

        ans += (larger * smaller);
    }
 
    return ans;
}
 
int main()
{
    int arr[] = { 1, 2, 3, 4, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf("Number of inversions are %d", solve(arr, n));
 
    return 0;
}

Output

Number of inversions are 2

C++

#include <bits/stdc++.h>
using namespace std;
int solve(int arr[], int n)
{
    int ans = 0;
     for (int j = 1; j < n - 1; j++)
    {
        int larger = 0;
        for (int i = 0; i < j; i++)
        {
            if (arr[i] > arr[j]) {
                larger++;
            }
        }
 
        int smaller = 0;
        for (int k = j + 1; k < n; k++)
        {
            if (arr[k] < arr[j]) {
                smaller++;
            }
        }
 

        ans += (larger * smaller);
    }
 
    return ans;
}
 
int main()
{
    int arr[] = { 1, 2, 3, 4, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout<<"Number of inversions are "<<solve(arr, n);
 
    return 0;}

Output

Number of inversions are 2

Python

def solve(arr):
 
    ans = 0

    for j in range(1, len(arr) - 1):
 
        larger = 0
        for i in range(j):
            if arr[i] > arr[j]:
                larger = larger + 1
 
        smaller = 0
        for k in range(j + 1, len(arr)):
            if arr[k] < arr[j]:
                smaller = smaller + 1
 

        ans += (larger * smaller)
 
    return ans
 
 
arr = [1, 2, 3, 4, 2, 1]
print("Number of inversions are", solve(arr))

Output

Number of inversions are 2

People are also reading:

• Merge Two Sorted Arrays in-place
• Longest subarray with sum as K
• Maximum of all Subarrays of size K
• Sort binary array in linear time
• Subarray with Sum k
• Find Maximum Subarray Sum
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Create a mirror of an m–ary Tree
• In-place vs out-of-place algorithms
• Hybrid QuickSort Algorithm