Inversion Count Editorial

Practice Problem Link: Inversion Count | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

The inversion count of an array denotes how far is the array from being sorted. If the array is sorted, the inversion count is 0. If the array is sorted in reverse order, the inversion count is maximum. More formally, the inversion count of an array A is the number of pairs (i, j) such A[i] < A[j] and i > j.

Given an array A, Calculate the inversion count of the array.

Naive Approach

The simple solution for the above problem is to traverse the array and count the inversions (i.e. Count all the elements after arr[i] that are smaller than arr[i]) for each valid i.

Analysis

• Time Complexity: O(n²)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int getInversionCount(vector<int> array) {
   int inversions = 0, n = array.size();
   for (int i = 0; i < n; i++) {
       for (int j = i + 1; j < n; j++) {
           if(array[i] > array[j]) {
               inversions++;
           }
       }
   }
   return inversions;
}

Java

class Solution {
   int getInversionCount(int[] array) {
       int inversions = 0, n = array.length;
       for (int i = 0; i < n; i++) {
           for (int j = i + 1; j < n; j++) {
               if(array[i] > array[j]) {
                   inversions++;
               }
           }
       }
       return inversions;
   }
}

Optimal Approach

An efficient way to solve this problem is based on merge sort algorithm. All that needs to be added is to keep the count of inversions while merging two subarrays.

• Since the array is divided into two equal parts, so the number of inversion for the array will be equal to the sum of the number of inversions in the first subarray, the number of inversions in the second subarray and inversion count while merging the two sorted subarrays.
• Let’s say the i-th element in the first subarray is greater than the j-th element in the second subarray. Since both the subarrays are sorted all the elements after i-th element in the first subarray will also be greater than the j-th element of the second subarray. This will give the inversion count for the j-th element in the second subarray.
• Create a recursive function to merge all the subarrays, in the same way, to keep the count of total inversions until the base condition is met i.e. subarray size is one. In this particular case, there will be zero inversions as the subarray is sorted.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(n)

Implementation

C++

int merge (vector<int> &arr, int low, int mid, int high) {
   int subArr1Size = mid - low + 1, subArr2Size = high - mid;
   vector<int> subArr1, subArr2;
   for (int i = 0; i < subArr1Size; i++) {
       subArr1.push_back (arr[low + i]);
   }
   for (int i = 0; i < subArr2Size; i++) {
       subArr2.push_back (arr[mid + 1 + i]);
   }
   int i = 0, j = 0, k = low, inversions = 0;
   while (i < subArr1Size && j < subArr2Size) {
       if( subArr1[i] <=  subArr2[j]) {
           arr[k] = subArr1[i];
           i++;
       } else {
           arr[k] = subArr2[j];
           j++;
           inversions += mid + 1 - (low + i);
       }
       k++;
   }
   while (i < subArr1Size) {
       arr[k++] = subArr1[i++];
   }
   while (j < subArr2Size) {
       arr[k++] = subArr2[j++];
   }
   return inversions;
}
int mergesort (vector<int> &arr, int low, int high) {
   int inversions = 0;
   if (high > low) {
       int mid = (high + low) / 2;
       inversions += mergesort (arr, low, mid);
       inversions += mergesort (arr, mid + 1, high);
       inversions += merge (arr, low, mid, high);
   }
   return inversions;
}
int getInversionCount(vector<int> array) {
   return mergesort(array, 0, array.size() - 1);
}

Java

class Solution {
   int merge (int[] arr, int low, int mid, int high) {
       int subArr1Size = mid - low + 1, subArr2Size = high - mid;
       int[] subArr1 = new int[subArr1Size];
       int[] subArr2 = new int[subArr2Size];
       for (int i = 0; i < subArr1Size; i++) {
           subArr1[i] = arr[low + i];
       }
       for (int i = 0; i < subArr2Size; i++) {
           subArr2[i] = arr[mid + 1 + i];
       }
       int i = 0, j = 0, k = low, inversions = 0;
       while (i < subArr1Size && j < subArr2Size) {
           if( subArr1[i] <=  subArr2[j]) {
               arr[k] = subArr1[i];
               i++;
           } else {
               arr[k] = subArr2[j];
               j++;
               inversions += mid + 1 - (low + i);
           }
           k++;
       }
       while (i < subArr1Size) {
           arr[k++] = subArr1[i++];
       }
       while (j < subArr2Size) {
           arr[k++] = subArr2[j++];
       }
       return inversions;
   }
   int mergesort (int[] arr, int low, int high) {
       int inversions = 0;
       if (high > low) {
           int mid = (high + low) / 2;
           inversions += mergesort (arr, low, mid);
           inversions += mergesort (arr, mid + 1, high);
           inversions += merge (arr, low, mid, high);
       }
       return inversions;
   }
   int getInversionCount(int[] array) {
       return mergesort (array, 0, array.length - 1);
   }
}