Count triplets which form an inversion in an array

Posted in

Count triplets which form an inversion in an array

Vinay Khatri
Last updated on September 23, 2022

    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:

    Leave a Comment on this Post

    0 Comments