Striver's SDE Sheet Journey - #12 Count inversions in an array
Tags: beginners, programming, dsa, java
Published: 2022-01-11 07:17:33

> **<u>Problem Statement</u> :-**

_Given an array of N integers, count the inversion of the array._
_An inversion is defined for a pair of integers in the array when the following two conditions are met._
1. `ARR[i] > ARR[j] `
2. `i < j`

**Input** :  `array = [2, 5, 1, 3, 4]`

**Result** : `4`

**Explanation**: _We have a total of 4 pairs which satisfy the condition of inversion. (2, 1), (5, 1), (5, 3) and (5, 4)._


##  <u>Solution 1</u>
_we can solve this problem by using two nested loop,but it will cost `n^2` time complexity._

**step-1** initialise a variable `pairs=0` .
**step-2** run a loop from `i=0` to `n`.
> **1.** run another loop from `j=i+1` to `n`.
 > > check, if `arr[i] > arr[j]` is true, then increase the inversion count.

**step-3** end.

## Java

```java
public class Solution {
    public static long getInversions(long arr[], int n) {
        long pairs =0;
        
     for(int i=0; i<arr.length;i++){
       
          for(int j=i+1; j<arr.length;j++){
              
              if(arr[i] > arr[j]) pairs++;
          }
      }
      return pairs;
    }
}
```

##  <u>Solution 2</u>
_we can also solve this problem by using the **Merge Sort** algorithm. if you know, how we merge two sorted subarrays in the merge sort algorithm then you can easily understand this solution._

while merging the subarrays, count inversion pairs, 
if an element of the left subarray is greater than an element of the right subarray.

let's visually understand how we solve this problem while merging two subarrays.

`Array = [5,3,2,1,4]`


![Count inversions in an array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/878b9aimaz5megwmyvjh.png)

as you can see `5` is greater than `3` which means it satisfies the first condition of inversion pairs and it also satisfies the second one,` i<j`.
we have found the first inversion pair while merging two subarrays.
pairs - `(5,3)`



![Count inversions in an array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ijbu41uyz8iqvfvcorpa.png)
`3 > 2` &` 5 > 2` this pairs also satisfy the both conditions then we will count them as inversion pairs.
pairs - `(3,2)` `(5,2)`



![Count inversions in an array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3ztzsljsq0um8s1rwh5j.png)
now this time, the left subarray element `1` is not greater than the right subarray element `4`, which does not satisfy the first condition of the inversion pairs.


![Count inversions in an array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h5jqcri3ou8tjcwzdnui.png)
`2 > 1` then we can makes - `(2,1)` `(3,1)` `(5,1)` pairs.
`2 < 4` doesn't satisfy the conditions.
`3 < 4` doesn't satisfy the conditions.
`5 > 4` then - `(5,4)`

## Java

```java
public class Solution {
    public static long getInversions(long arr[], int n) {
        // Write your code here.
        long[] ans = new long[1];
        mergeSort(arr,0,arr.length-1,ans);
   
      return ans[0];
    }
    
    private static void mergeSort(long[] arr,int left,int right,long[] ans){

    // return if arr size becomes 1
    if(left >= right) return;


    // calculate the mid
    int mid = ( left + right ) / 2;


    mergeSort(arr,left,mid,ans);
    mergeSort(arr,mid+1,right,ans);

    merge(arr,left,mid,right,ans);

   }
    
     private static void merge(long[] arr,int left,int mid,int right,long[] ans){

    // calculate the size of left & right subarrays
    int leftArrSize = mid - left+1;
    int rightArrSize = right - mid;

    // initialise temp subarrays
    long[] leftArr = new long[leftArrSize];
    long[] rightArr = new long[rightArrSize];

    // copy left & right array into temp arrays
    for (int i = 0; i < leftArrSize; ++i)
      leftArr[i] = arr[left + i];
    for (int j = 0; j < rightArrSize; ++j)
    rightArr[j] = arr[mid + 1 + j];

    // set initial indexes of subarrays
    int leftPointer = 0;
    int rightPointer = 0;
    int arrPointer = left;

    // copy temp subarrays, in ascending order
    while(leftPointer < leftArrSize && rightPointer < rightArrSize ){

      if(leftArr[leftPointer] <= rightArr[rightPointer]){
        arr[arrPointer] = leftArr[leftPointer];
        arrPointer++;
        leftPointer++;
      }else{
        arr[arrPointer] = rightArr[rightPointer];
        arrPointer++;
        rightPointer++;
         ans[0] += leftArrSize - leftPointer; 
      }
    }


    // copy the remaining elements of left subarray into a marge array
    while(leftPointer < leftArrSize){
      arr[arrPointer] = leftArr[leftPointer];
      arrPointer++;
      leftPointer++;
    }

    // copy the remaining elements of right subarray into a merge array
    while(rightPointer < rightArrSize){
      arr[arrPointer] = rightArr[rightPointer];
      arrPointer++;
      rightPointer++;
    }



   }

}
```


_The Time & Space complexity will be the same as the Merge Sort algorithm, **O(Nlogn)**, bcoz we add some lines of code for counting the inversion pairs._

---

_thank you for reading this article, if you find any mistakes, let me know in the comment section and save it for future use._