1.
Introduction-
2.
Solution Approach
2.1.
Algorithm -
2.2.
C++ code:
2.3.
Algorithm Complexity:
2.3.1.
Time Complexity: O(N * K * log(N))
2.3.2.
Space Complexity: O(N * K)
3.
FAQs
4.
Key takeaways-
Last Updated: Mar 27, 2024

# Count of Inversion of size K in a given array

Riya
1 upvote

## 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[ i2 ], ……, arr[ iK ]” such that:

arr[ i] > arr[ i2 ] > ……> arr[ iK ]  and

0 <= i1 < i2 <.......< iK
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.

## 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.

### 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).

## FAQs

1. What is a Binary Indexed Tree?
A Binary indexed tree, also known as Fenwick tree, is a data structure that stores the elements in an array and helps to calculate the prefix sum efficiently. This data structure is based on the fact that every positive integer can be represented as the sum of powers of 2.

2. How has Binary Indexed Tree helped to find an efficient solution for this problem?
In the above problem to find the count of inversions of K, we have created 'K' binary indexed trees to store the count of the number of inversions of size i = 1 to i = k. We have stored it in a two-dimensional array "bit[][]," where bit[i][j] stores the number of inversions of length 'i' which start with 'j' and have traversed the array from its last element and updated the binary indexed tree in O(log N) time for each of the 'K' binary indexed trees. So, the overall time complexity has been reduced to O(N*K*log(N))..

## Key takeaways-

This article discussed the problem "Count Inversions of size K in a given array," an approach to solve this problem using the Fenwick tree, its C++ implementation, and its time and space complexity. If you want to solve problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass