AI Features
Home
Courses
Algorithms for Coding Interviews in Java

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

Java
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 ...

Ask