Count Inversions

By | November 16, 2021
Count Inversions

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.

Vamware

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:

Author: Vinay Singh

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.