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.

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:

• Sort elements by their frequency and index
• AVL Tree
• Fibonacci Series
• Circular Doubly Linked List
• Depth First Search(DFS)- DSA
• Circular Linked List
• Types of Data Structure
• Tree vs Graph
• What is Data Structure?
• Algorithms Basics