Zero to SDE : Count Inversions - DSA- sorting

Given an array of integers. Find the Inversion Count in the array.

Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0.
If an array is sorted in the reverse order then the inversion count is the maximum.
Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Example 1:

Input: N = 5, arr[] = {2, 4, 1, 3, 5}
Output: 3
Explanation: The sequence 2, 4, 1, 3, 5 
has three inversions (2, 1), (4, 1), (4, 3).

Understanding the problem:

What is an inversion? How do we identify it?

Imagine you’re dealing with a bunch of numbers. You’re not just sorting them, you’re counting how messed up they are. Yep, that’s right — we’re talking about inversions.

So, what are these inversions? Well, it’s like when you’re supposed to be tidy and sorted, but you end up all jumbled. If you’re already sorted, inversions are zero. But if you’re all over the place, they’re as wild as can be!

Formally, an inversion happens when one number looks down on another, saying, “Hey, I’m bigger than you, and you’re behind me!” Rude, right?

Let’s kick off the problem :

N = 5, arr[] = {2, 4, 1, 3, 5}
             i= 0  1  2  3  4
At index=0,
observe all the elements before index 0 and check if any element is greater than the current element.
If you find such an element, you've identified your first inversion.
Oops, it's at the first index.

At index=1,
All elements before index 1 are 2.
Repeat the same process.
Sorry, there is no inversion.

At index=2,
All elements before index 2 are 2 , 4.
Once again, follow the same procedure. 
Ah, here we have an inversion.
How? - As previously described, we inspect all the elements before the current index 2. At indices 0 and 1, we find elements 2 and 4, respectively, which are greater than element 1.

At index=3,
All elements before index 2 are 2 , 4 and 1.
Repeat the procedure.
Indeed, another inversion is found.
How? - Similar to earlier steps, we examine all the elements before the current index 3. At indices 0 and 1, we find elements 2 and 4, respectively, which are greater than element 3.

At index=4,
All elements before index 2 are 2 , 4 , 1 and 3.
Once again, repeat the procedure.
Yes, another inversion is identified here.
At index 1, element 4 is greater than element 3.

At index=5,
All elements before index 2 are 2 , 4 , 1 , 3, 5.
Since it's the maximum element, no inversion will be found here.

Now that we understand the problem, let's delve into solving it.

Now, how do we solve the problem?

Okay then, buckle up yourself, we’re going dive into the algorithm design part.

Brute Approach:

As you might recall, we’re examining the elements preceding the current element. Utilizing array and loop concepts, we iterate through the elements one by one and, within the loop, once again examine the elements before the current element.

void countInversion(){
    int arr[]={2, 4, 1, 3, 5};
    int n=5;
    int count=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
           if(arr[j]>arr[i]){
              count++;
           } 
        }
    }
}

Time Complexity: O(n^2)

Space Complexity: O(1)

Better Approach:

Before delving into this approach, it’s essential to have a basic understanding of Merge Sort.

Here, we use the divide and conquer concept:

1. Divide the array until we obtain a size of 1 element, which is inherently sorted.
2. Subsequently, merge the two divided arrays. Before merging, we ascertain whether the element in the first array is smaller. If so, it’s added to the final array. Otherwise, the element from the second array is added to the final array, along with a check for inversions, as we assume both arrays obtained after division are already sorted.

The count variable accumulates the count of inversions during the merge process.

Time Complexity: O(nlogn)

Space Complexity: O(n)

I hope this clarifies the concepts without necessitating the sharing of code. To enhance your expertise, I encourage you to implement the code yourself.

I hope you find this article helpful and interesting. Please like and share it with your friends who want to learn about this topic.

Happy Coding :)

~ Nazim Qureshi