Count of Inversion of size K in a given array

Introduction-  

This blog will discuss the problem "Count of Inversions of size K in a given array". In this problem, we will be given an array containing ‘N’ distinct integers and a positive integer ‘K’. We have to find the count of inversions of size K in the given array.  Before proceeding further, let’s understand what do we mean by an inversion of size K in an array.

Let’s say we have an array ‘arr’ having N integers. An inversion of size K (K <= N) in the array will be a subsequence “arr[ i₁ ], arr[ i₂ ], ……, arr[ i_K ]” such that:

arr[ i₁ ] > arr[ i₂ ] > ……> arr[ i_K ]  and

0 <= i₁ < i₂ <.......< i_K
Let's take an example to understand the problem:

Suppose we have the following given information -
arr = { 8, 7, 1, 6, 2}

N = 5

K = 3

We have to find the count of inversions of length 3 (K = 3) in the given array.

Inversions of length 3 in the given array are:

{8, 7, 1}

{8, 7, 6}

{8, 7, 2}

{8, 6, 2}

{7, 6, 2}

Here, we can see that there is a total of five inversions of length three in the given array. 

Now that we understand the problem, let's discuss the approach to solve it in the next section.

Also read, Euclid GCD Algorithm

Solution Approach

This section will discuss an approach to solve the problem of finding the count of inversions of size K in a given array using a Binary Indexed Tree, also called a Fenwick Tree. For creating a binary indexed tree, first convert the given array to a permutation of integers from 1 to N, maintaining the relative order of values of the array elements.

For example array { 8, 7, 1, 6, 2} will be converted to {5, 4, 1, 3, 2}

Now, the approach is to create a two-dimensional array "bit[][]" to create 'K' Fenwick trees. Here bit[i][j] stores the number of inversions of length 'i', which start with 'j.'

Fill the array' bit[i][j]' starting from the last element of the array. Finally, the total number of inversions of length K will be the sum of bit[K][i], where 1 <= i <=N, as bit[K][i] denotes the number of inversions of size K which starts from 'i'.

Algorithm -

Step 1. First, write the main function. Inside the main function, call the function "convertToPermutation()" function to convert the given array to a permutation of numbers from 1 to N, maintaining the relative order of values of the array elements. Next, call the function "findInversionsCount()" to find the count of inversions of size K in the given array.

Step 2. Create the function "convertToPermutation()" to convert the given array to a permutation of numbers from 1 to N, maintaining the relative order of values of the array elements. Inside the function, first, create a copy 'temp' of the given array 'arr' and then traverse array 'arr .'For each element in 'arr,' find the number of elements less than or equal to it and then update its value. 

Step 3. Globally define bit[K][N] to store K binary indexed trees, where bit[i][j] denotes the number of inversions of length 'i' starting with 'j .'Create the function "findInversionsCount()" to find the count of inversions of size K in the given array. Inside the function, start iterating 'arr' from its last element to the first element. For each element ‘arr[i]’, first, update binary indexed tree for length = 1. Then run a loop and update each binary indexed tree. Finally, return sum of bit[K][i], where 1<=i<=N.

Step 4. Create function "update()" to update a binary indexed tree and "findSum()" to find the sum of inversions of a given length using the binary indexed tree.

C++ code:

// C++ program to find the count of inversions of size k in a given array using Binary Indexed Tree
#include <bits/stdc++.h>
using namespace std;


// Varriable to store set of fenwick trees
int bit[51][100001] = { 0 };


// Function to Convert the array to a permutation of integers from 1 to N maintaining the relative order of values of array elements
void convertToPermutation(int arr[], int N)
{


	// Create a copy of given array 'arr'
	int temp[N];
	for (int i = 0; i < N; i++)
	{
	temp[i] = arr[i];
	}


	// Sorting the copied array
	sort(temp, temp + N);


	// Traverse all array elements and convert it to into a number between 1 and N maintaining the relative order of values
	for (int i = 0; i < N; i++) 
	{

		// Pointer to the first element greater than or equal to arr[i]
		int* lb = lower_bound(temp, temp + N, arr[i]);

		// Update arr[i] with a number 1 more than the number of elements less than it in the original array
		arr[i] = (lb - temp) + 1;
              	
	}
}


// update function
void update(int l, int i, int val, int n)
{


    // Traversing the l'th binary indexed tree 
    while (i <= n) 
    {
        bit[l][i] = bit[l][i] + val;
        i = i + (i & (-i));
    }
}


// function to get the sum.
int FindSum(int l, int i)
{
    int sum = 0;
  
    // Traversing the t'th BIT
    while (i > 0) 
    {
        sum = sum + bit[l][i];
        i = i - (i & (-i));
    }
    
    return sum;
}


// Function to return the count of inversions of size k in a given array
int findInversionsCount(int arr[], int n, int k)
{

	// Start from the last element of the array
	for (int i = n - 1; i >= 0; i--)
	{
		int curr = arr[i];


		// update first binary indexed tree
		update(1, curr, 1, n);


		// update bit array for all length
		for (int j = 1; j < k; j++) 
		{

			// Count of inversions of length j starting with (curr-1)
			int s = FindSum(j, curr - 1);


			// update (j+1)th binary indexed tree 
			update(j + 1, curr, s, n);
		}
	}


	// final result
	return FindSum(k, n);
}


// Main Function
int main()
{

	// Variable to store number of elements in the given array
	int N = 5;

	// Given array
	int arr[] = { 8, 7, 1, 6, 2}; 

	// Given value of K
	int K = 3;

	// Convert the array to a permutation of integers from 1 to N maintaining the relative order of values of array elements
	convertToPermutation(arr, N);

	// Call the function to find the count of inversions of size k in a given array
	int inversionsCount = findInversionsCount(arr, N, K);

	cout <<"The count of inversions of size "<< K <<" in a given array is: " << inversionsCount;
	return 0;
}

Output:
The count of inversions of size 3 in a given array is: 5

Algorithm Complexity: 

Time Complexity: O(N * K * log(N))

In the function "findInversionsCount()" to find the count of inversions of size K in a given array, we have created a for loop to iterate through each element of the array, and for each element of the array, we have maintained K binary indexed tree, for which we have called "update()" and "findSum()" functions which take O(log N) time. So, the overall time complexity is O(N * K * log(N)), where 'N' is the number of elements in a given array.

Space Complexity: O(N * K) 

In the above program to find the count of inversions of size K in a given array, we have created a bit[N][K] array to store K binary indexed tree, each having N nodes. So, the space complexity is O(N * K).