Count inversions in a permutation of first N natural numbers

0 0 5 minutes read

Given an array, arr[] of size N denoting a permutation of numbers from 1 to N, the task is to count the number of inversions in the array.
Note: Two array elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Examples:

Input: arr[] = {2, 3, 1, 5, 4}
Output: 3
Explanation: Given array has 3 inversions: (2, 1), (3, 1), (5, 4).

Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has 2 inversions: (3, 1), (3, 2).

Different methods to solve inversion count has been discussed in the following articles:

Approach: This problem can be solved by using binary search. Follow the steps below to solve the problem:

Store the numbers in the range [1, N] in increasing order in a vector, V.
Initialize a variable, ans as 0 to store the number of inversions in the array, arr[].
Iterate in the range [0, N-1] using the variable i
- Store the index of occurrence of arr[i] in vector V in a variable index.
- Add the count of numbers having positions less than the index that are present in the vector, V since they are smaller than the current element and thus form inversions.
- Remove the element at position index from the vector, V.
Print the value of ans as the result.

Below is the implementation of the above approach:

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of inversions in
// a permutation of first N natural numbers
int countInversions(int arr[], int n)
{
    vector<int> v;
 
    // Store array elements in sorted order
    for (int i = 1; i <= n; i++) {
        v.push_back(i);
    }
 
    // Store the count of inversions
    int ans = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // Store the index of first
        // occurrence of arr[i] in vector V
        auto itr = lower_bound(
            v.begin(), v.end(), arr[i]);
 
        // Add count of smaller elements
        // than current element
        ans += itr - v.begin();
 
        // Erase current element from
        // vector and go to next index
        v.erase(itr);
    }
 
    // Print the result
    cout << ans;
 
    return 0;
}
 
// Driver Code
int main()
{
 
    // Given Input
    int arr[] = { 2, 3, 1, 5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    countInversions(arr, n);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.Vector;
 
class GFG{
 
// Function to count number of inversions in
// a permutation of first N natural numbers
static void countInversions(int arr[], int n)
{
    Vector<Integer> v = new Vector<>();
 
    // Store array elements in sorted order
    for(int i = 1; i <= n; i++)
    {
        v.add(i);
    }
 
    // Store the count of inversions
    int ans = 0;
 
    // Traverse the array
    for(int i = 0; i < n; i++) 
    {
         
        // Store the index of first
        // occurrence of arr[i] in vector V
        int itr = v.indexOf(arr[i]);
 
        // Add count of smaller elements
        // than current element
        ans += itr;
 
        // Erase current element from
        // vector and go to next index
        v.remove(itr);
    }
 
    // Print the result
    System.out.println(ans);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given Input
    int arr[] = { 2, 3, 1, 5, 4 };
    int n = arr.length;
 
    // Function Call
    countInversions(arr, n);
}
}
 
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
from bisect import bisect_left
 
# Function to count number of inversions in
# a permutation of first N natural numbers
def countInversions(arr, n):
     
    v = []
 
    # Store array elements in sorted order
    for i in range(1, n + 1, 1):
        v.append(i)
 
    # Store the count of inversions
    ans = 0
 
    # Traverse the array
    for i in range(n):
         
        # Store the index of first
        # occurrence of arr[i] in vector V
        itr = bisect_left(v, arr[i])
 
        # Add count of smaller elements
        # than current element
        ans += itr
 
        # Erase current element from
        # vector and go to next index
        v = v[:itr] + v[itr + 1 :]
 
    # Print the result
    print(ans)
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    arr = [ 2, 3, 1, 5, 4 ]
    n = len(arr)
 
    # Function Call
    countInversions(arr, n)
     
# This code is contributed by SURENDRA_GANGWAR

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
    // Function to count number of inversions in
    // a permutation of first N natural numbers
    static void countInversions(int[] arr, int n)
    {
        List<int> v = new List<int>();
 
        // Store array elements in sorted order
        for (int i = 1; i <= n; i++) {
            v.Add(i);
        }
 
        // Store the count of inversions
        int ans = 0;
 
        // Traverse the array
        for(int i =0 ;i <n;i ++){
 
            // Store the index of first
            // occurrence of arr[i] in vector V
            int itr = v.IndexOf(arr[i]);
         
 
            // Add count of smaller elements
            // than current element
            ans += itr;
 
            // Erase current element from
            // vector and go to next index
            v.RemoveAt(itr);
        }
 
        // Print the result
        Console.WriteLine(ans);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
 
        // Given Input
        int[] arr = { 2, 3, 1, 5, 4 };
        int n = arr.Length;
 
        // Function Call
        countInversions(arr, n);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to count number of inversions in
// a permutation of first N natural numbers
function countInversions(arr, n)
{
    var v = [];
    var i;
     
    // Store array elements in sorted order
    for(i = 1; i <= n; i++)
    {
        v.push(i);
    }
 
    // Store the count of inversions
    var ans = 0;
 
    // Traverse the array
    for(i = 0; i < n; i++) 
    {
         
        // Store the index of first
        // occurrence of arr[i] in vector V
        var index = v.indexOf(arr[i]);
 
        // Add count of smaller elements
        // than current element
        ans += index;
 
        // Erase current element from
        // vector and go to next index
        v.splice(index, 1);
    }
 
    // Print the result
    document.write(ans);
}
 
// Driver code
 
// Given Input
var arr = [ 2, 3, 1, 5, 4 ];
var n = arr.length;
 
// Function Call
countInversions(arr, n);
 
// This code is contributed by bgangwar59
 
</script>

Output:

Time Complexity: O(N*log(N))
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!