Approach 1
We will solve this problem using a Binary Indexed Tree (Fenwick Tree). The idea is to count the elements greater than a[i] for all i to the left of it, i.e., a[i] < a[j], i > j.
Fenwick tree offers us the option to find the sum of elements up to some index i and update an element at index i to some new value.
We will be using this to build our solution. We find the maximum element in the array and make our BIT(Binary Indexed Tree) array of size= maximum element + 2. Initially, the whole BIT array is filled with 0’s. We can set 1 at index a[i], for each i and count all the indexes less than equal to a[i] by querying the sum of all elements till index a[i]. The sum till a[i] will give you the count of elements (a[j]) less than equal to a[i], where j <= i.
Using the above, we can find the larger elements to the left of a[i] as i + 1 - count of elements less than equal to a[i].
The code follows the following steps to implement the above idea.
- Find the maximum element in the array, make a BIT vector with size max element + 2 all set to 0 in the beginning,
- For every i < n, we set index a[i] to 1.
- We then count the elements less than or equal to a[i] on the left of i by querying for sum up to a[i].
- i + 1 - count of elements less than equal to a[i] on the left will give you all elements on the left that are greater than a[i].
- Add this count to inv_count, our final answer. After doing the above step for every i, we return and print the answer.
Also read, Euclid GCD Algorithm
Code for approach 1 in C++
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
/* required functions for fenwick tree, learn more about how these work through the shared links*/
void add(vector<int>& BIT, int idx, int val){
idx += 1;
while(idx < BIT.size()){
BIT[idx] += val;
idx += idx & -idx;
}
}
int query(vector<int>& BIT, int idx){
idx += 1;
int sum = 0;
while(idx){
sum += BIT[idx];
idx &= idx - 1;
}
return sum;
}
int CountInversions(vector<int> a, int n){
int mx = *max_element(a.begin(), a.end());
vector<int> BIT(mx + 2, 0);
int inv_count = 0;
for(int i = 0; i < n; i++){
// increasing index a[i] by 1
add(BIT, a[i], 1);
// count of numbers greater than a[i] before it
// being added to the inverse count
inv_count += i - query(BIT, a[i]) + 1;
}
return inv_count;
}
int32_t main(){
// change input here
vector<int> a = {6, 4, 3, 2, 1};
int n = a.size();
cout << CountInversions(a, n) << endl;
}
Output
10
Time Complexity
The code’s complexity is O(Nlog(maximumElement)), N updates and queries take O(Nlog(maximumElement)) time (each query and update take O(log(maximumElement)) time individually).
Space Complexity
O(maximumElement) extra space is needed in this approach and it can easily solve the version of the problem where 0 < a[i] < 106. However, it will take way too much space in the version -109 < a[i] < 109 and won’t support negative numbers.
Approach 2
In addition to the previous approach, we use the fact that if we replace an element by its position in the same sorted array, the inverse count will remain the same.
The fact holds that the number of elements greater than a[i] for some i remains the same on the left of i. The inversion count will also thus stay the same.
The code follows the following steps to implement the above idea.
- Make a copy B of array A.
- Sort array B.
- Search the position of all the elements (a[i]) using binary search in B. Make the newly found position the new value of a[i].
- This will restrict the value of a[i], now it will be in the range 0 <= a[i] < N.
- Now we will follow the steps in Approach 1.
Code for approach 2 in C++
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
void add(vector<int>& BIT, int idx, int val){
idx += 1;
while(idx < BIT.size()){
BIT[idx] += val;
idx += idx & -idx;
}
}
int query(vector<int>& BIT, int idx){
idx += 1;
int sum = 0;
while(idx){
sum += BIT[idx];
idx &= idx - 1;
}
return sum;
}
int CountInversions(vector<int> a, int n){
vector<int> BIT(n + 1, 0);
vector<int> b = a;
sort(b.begin(), b.end());
for(int i = 0; i < n; i++){
a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
}
// now for all i, 0 <= a[i] < n
int inv_count = 0;
for(int i = 0; i < n; i++){
// increasing index a[i] by 1
add(BIT, a[i], 1);
// count of numbers greater than a[i] before it
// being added to the inverse count
inv_count += i - query(BIT, a[i]) + 1;
}
return inv_count;
}
int32_t main(){
// change input here
vector<int> a = {2, 1, 2, 5, 999999, 3};
int n = a.size();
cout << CountInversions(a, n) << endl;
}
Output
3
Time Complexity
The code’s complexity is O(Nlog(N)), binary searching for N elements in an N sized array takes O(Nlog(N)) time, and N updates and query also take O(Nlog(N)) time.
Space Complexity
O(N) extra space is needed in this approach, unlike the previous approach, and we can also find inversions in an array with negative numbers.
Frequently Asked Questions
1. Where can I learn more about Fenwick trees and how they work?
You can learn more about the Fenwick tree from here and can try a related problem from here. I recommend you write the code for a Fenwick tree and justify to yourself that it will take O(log(N)) for query and update.
2. What are the advantages of the Fenwick tree against the Segment tree?
While more powerful in most cases, Segment trees are not straightforward to implement and are generally slower for the same use as the code involves more operations and is often recursive. They also take a lesser amount of memory when compared to Segment trees.
Key Takeaways
The article helps us implement our knowledge of the Fenwick tree into a real problem and provides a simple solution to the problem of finding the inversion count independent of the language you use. To understand the blog well, read about Inversion count and other methods to calculate inversion count here and the Fenwick tree here.
Learn more about the C++ STL library from here if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.
Happy learning!
39+ registered 