Algorithms for Coding Interviews in Java/

...

/

Solution: Inversion Count in an Array

Solution: Inversion Count in an Array

This lesson explains how to calculate the inversion count in a divide and conquer paradigm.

We'll cover the following...

Solution# 1

Press + to interact
class Inversion {
 public static int InvCount(int[] arr) {
  int size = arr.length;
  int count = 0; // variable to store inversion count
  for (int curr = 0; curr < size - 1; curr++)
   for (int right = curr + 1; right < size; right++)
    if (arr[curr] > arr[right])
     count++;
  return count;
 }
 public static void main(String[] args) {
  int[] arr = {
   3,
   2,
   8,
   4
  };
  System.out.println(Arrays.toString(arr) + "  --->  " + InvCount(arr));
 }
}

The naive solution to this problem would be:

  1. Traverse the whole array while keeping a variable to store the inversion count, count (lines 4-8).

  2. Whenever you hit a number on the right of the current index, such that arr[curr] > arr[right], increment the variable count by 1 (lines 7-8).

  3. Return the final count when the whole array is traversed (line 10).

Time Complexity

The array is traversed once for each existing element in it. This approach is inefficient because it takes O(n2 ...