Count Inversions in an array

This question is asked from me in Goldman Sachs round 2.

This is the implementation of the Merge Sort Algorithm,

https://www.geeksforgeeks.org/counting-inversions/

Input: arr[] = {8, 4, 2, 1}
Output: 6

Explanation: Given array has six inversions:
(8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).


Input: arr[] = {3, 1, 2}
Output: 2

Explanation: Given array has two inversions:
(3, 1), (3, 2)

We need to calculate the inversions in the array,

if(ar[i]>ar[j]) && i<j.

Here we are simply doing the merge sort where while merging we are checking if (ar[i]>ar[j]) && i<j then increment the count of inversion,

also if say 2 arrays are there like {3,27,38,43} and {9,10,82} here 27 > 9 So, the total inversion is all elements right to 27 including 27 for an element 9 because if 27>9 then all the elements right to it also must be greater than 27 as both of the 2 arrays are sorted.

Here the sample code for the same.

package com.interview;
public class Solution {
public static void main(String[] args) {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int count= sort(arr, 0, arr.length - 1);
System.out.println(count);
for (int i : arr)
System.out.print(i + " ");
}
public static int sort(int arr[], int left, int right) {
int count = 0;
if (left < right) {
int mid = left + (right - left) / 2;
count += sort(arr, left, mid);
count += sort(arr, mid + 1, right);
count += merge(arr, left, mid, right);
}
return count;
}
public static int merge(int[] arr, int left, int mid, int right) {
int inversion = 0;
int size1 = mid - left + 1;
int size2 = right - mid;
int leftArr[] = new int[size1];
int rightArr[] = new int[size2];
for (int i = 0; i < size1; i++)
leftArr[i] = arr[i + left];
for (int j = 0; j < size2; j++)
rightArr[j] = arr[j + 1 + mid];
int k = left;
int i = 0, j = 0;
while (i < size1 && j < size2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
inversion += (mid + 1) - (left + i);
}
k++;
}
while (i < size1) {
arr[k] = leftArr[i];
k++;
i++;
}
while (j < size2) {
arr[k] = rightArr[j];
k++;
j++;
}
return inversion;
}
}

Happy Coding!!