Count Inversions

Posted in

Count Inversions
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    Problem

    Given an array of integers, count the number of inversions present in it. An inversion is such that arr[i] > arr[j] and i<j.

    Sample Input

    [3, 4, 1]

    Sample Output

    Inversion count is 2

    Approach 1

    Traverse through the array, and for every index, find the number of smaller elements on its right side. This can be done using nested loops. Sum up the counts for all indexes in the array. The time complexity of this approach is O(N2).

    C Programming

    #include <stdio.h>
    #include <stdlib.h>
    
    int solve(int arr[], int n)
    {
        // nested loops
        int ans = 0;
    
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                if (arr[i] > arr[j])  //if found the required condition
                    ans++;
        return ans;
    }
    
    int main()
    {
    
        int arr[] = {3, 4, 1 };
        int n = sizeof(arr) / sizeof(arr[0]);
        printf(" Inversion count is %d ",solve(arr, n));
    
        return 0;
    
    }

    Output

    Inversion count is 2

    Python Programming

    def solve(arr, n):
    
    	ans = 0
            # use two nested loops
    	for i in range(n):
    		for j in range(i + 1, n):
    			if (arr[i] > arr[j]):    #if condition is satisfied
    				ans += 1
    
    	return ans
    
    arr = [3, 4, 1]
    n = len(arr)
    print("Inversion count is", solve(arr, n))
    

    Output

    Inversion count is 2

    Approach 2

    We can solve this problem using sets in C++. The sets in C++ implement Self-Balancing BST . Following is an algorithm to implement this approach Create an empty set and insert the first element of the array into the set. Also, initialize ans variable to 0, which stores inversion count. Iterate from 1 to n -1 and

    1. Insert arr [i] into the set.
    2. Find the upper bound of arr [i] in the set.
    3. Find the distance of the upper bound with the last element of the set and add this distance to ans.

    The worst-case time complexity of this approach can go upto O(N2), but still, the computation time is relatively less than the brute force method.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    int solve(int arr[],int n)
    {
    
        multiset<int> set1;
        set1.insert(arr[0]);
        int ans = 0;
        multiset<int>::iterator itset1; 
    
        for (int i=1; i<n; i++)
        {
            // insert element into the set
            set1.insert(arr[i]);
    
            // find the upper bound of the element
            itset1 = set1.upper_bound(arr[i]);
    
            // add distance to the answer
            ans += distance(itset1, set1.end());
        }
        return ans;
    }
    
    int main()
    {
    
       int arr[] = {3, 4, 1};
        int n = sizeof(arr)/sizeof(int);
        cout << "Inversion count is " << solve(arr,n);
        return 0;
    }

    Output

    Inversion count is 2

    People are also reading:

    Leave a Comment on this Post

    0 Comments