Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Inversion Count in an Array

Explore how to apply divide and conquer techniques to count inversions in an array efficiently. This lesson guides you through implementing both a naive O(n²) approach and an optimized O(n log n) solution using recursion and merging strategies, enhancing your skills in algorithm optimization for coding interviews.

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 existing element in it. This approach is inefficient because it takes O(n2 ...