Problem

Given an integer array, count the number of inversions.

What is an inversion?

This was taught in Algorithms: Design and Analysis Part I on coursera - how to count inversions.

Inversion count is the distance of order of elements in an array from the the sorted order i.e. it indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.

In other words, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Examples

Example 1:

Input: arr = [2, 5, 4, 6, 0]
output: 4
Explanation - (2, 0), (5, 4), (5, 0),(4, 0) and (6, 0).

Example 2:

Input: arr[] = [3, 1, 2]
Output: 2
Explanation: Given array has two inversions: (3, 1), (3, 2)

Solution

Method 1 - Brute Force

The brute force solution for this problem would be to traverse the array from right to left and count number of smaller element on the right in O(n^2).

Code

Java
public int countInversions(int arr[]) {
	int count = 0;
	int i, j;

	for (i = 0; i < n - 1; i++) {

		for (j = i + 1; j < n; j++) {
			if (arr[i] > arr[j]) {
				count++;
			}
		}
	}

	return count;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Divide and Conquer

Can we do it a better way? Yes.

We’ll use the divide and conquer method and piggyback on the MergeSort algorithm to do it in O(nlogn). By counting the number of inversions, we will also be sorting it.

An observation is that if we split the array into two halves such that both halves are sorted in increasing order then inversion count of each partition is 0. However, there might be cross inversion across the partitions. For example , Left=[2, 5, 6] and Right=[1, 3, 8]. Then we can see that there are 5 cross inversions (2,1), (5,1), and (5,3), (6,1), (6,3). But computing such cross inversion in pairwise manner would take O(n^2) and certainly not worthy.

By splitting the array in half, we know that:

total inversions = inversions in left + inversions in right + split inversions

But, the number of split inversions will actually be counted when we do the merge subroutine. So the way merge works is that it will keep track of two pointers, one to the front of each half array. It will take the smaller element and increment the pointer. If an element is taken from the second array, we know that it must be smaller than the element in the first subarray, and subsequently every element thereafter. Then we can just sum up the number of elements left in the first array each time the second subarray is chosen from before the first.

Code

Java
public int countInversions(int[] a) {
	return countInversions(a, 0, a.length - 1);
}


private int countInversions(int[] arr, int start, int end) {
	int count = 0;

	if (start < end) {
		int m = (start + end) / 2;

		// Total inversion count = left subarray count
		// + right subarray count + merge count

		// Left subarray count
		count += countInversions(arr, start, m);

		// Right subarray count
		count += countInversions(arr, m + 1, end);

		// Merge count
		count += countSkipInversions(arr, start, m, end);
	}

	return count;
}


private int countSkipInversions(int[] arr, int l, int m, int r) {
	// Left subarray
	int[] left = Arrays.copyOfRange(arr, l, m + 1);

	// Right subarray
	int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

	int i = 0, j = 0, k = l, swaps = 0;

	while (i < left.length && j  <  right.length) {
		if (left[i] <= right[j]) {
			arr[k++] = left[i++];
		} else {
			arr[k++] = right[j++];
			swaps += (m + 1) - (l + i);
		}
	}

	// Fill from the rest of the left subarray
	while (i < left.length) {
		arr[k++] = left[i++];
	}

	// Fill from the rest of the right subarray
	while (j < right.length) {
		arr[k++] = right[j++];
	}

	return swaps;
}

Complexity

  • Time Complexity: O(n log n), The algorithm used is divide and conquer, So in each level one full array traversal is needed and there are log n levels so the time complexity is O(n log n).
  • Space Compelxity: O(1), No extra space is required.

Here is alternative code:

int countInversions(int[] a) {
    return countInversions(a, 0, a.length, new int[a.length]);
}

int countInversions(int[] a, int start, int end, int[] t) {
    if (start == end - 1)
        return 0;
    int mid = (start + end) / 2;
    int x = countInversions(a, start, mid, t);
    int y = countInversions(a, mid, end, t);
    int z = subroutine(a, start, mid, end, t);
    return x + y + z;
}

int subroutine(int[] a, int start, int mid, int end, int[] t) {
    int i = start;
    int j = mid;
    int k = i;
    int count = 0;
    while (i < mid && j < end) {
        if (a[i] < a[j])
            t[k++] = a[i++];
        else {
            t[k++] = a[j++];
            count += (mid - i);
        }
   }
    System.arraycopy(a, i, t, k, mid - i);
    System.arraycopy(a, j, t, k, end - j);
    System.arraycopy(t, start, a, start, end - start);

    return count;
}

Method 3 - Using Self Balanced Binary Tree, O(NlgN)

But we can do it more efficiently using balanced BST such as AVL tree or Red black tree. Observe that, If a key is greater than root, then it is greater than all the nodes in left subtree of root.

So, We will consider each number in an array as a BST node and insert them in a AVL tree one by one from right to left. During each insert we will keep updating the size of left subtree at the node being inserted. This will give us our desired smaller element count. We also need to handle balancing the tree while insert.

A balance tree got imbalanced on an insert when the insert on a subtree rooted at a node x makes difference between left subtree and right subtree height more than 1. We will have to consider 4 cases:

  1. Insert-in-left-of-left-subtree of x: we can balance by rotating x right
  2. Insert-in-right-of-right-subtree of x: we can balance by rotating x left
  3. Insert-in-right-of-left-subtree of x: we need two rotations: balance left of x by rotating left. And then a right rotation of x.
  4. Insert-in-left-of-right-subtree of x: we need two rotations: balance right of x by rotating right. And then a left rotation of x.

Time complexity will be O(nlgn) and space is O(n).

Method 4 - Using Insertion Sort, O(n+k)

If we know number of inversions(k) are quite low, i.e. n >> k, we can use insertion sort. Merge sort’s best-case time is still O(n log n), whereas insertion sort’s best case is O(n).

Code

Java
for (int i = 1; i < n; i++) {
    int temp = A[i];
    int j = 0;
    for (j = i - 1; j >= 0 && temp < A[j]; j--) {
        A[j + 1] = A[j];
        k++;  // Number of inversions
    }
    A[j + 1] = temp;
}

Dry Run

Example, if we have {2,1,5,3,4}. Here we have 2 inversions:
2 > 1, 5>3…rest looks okay.

i = 1, temp = 1
j = 0, A[j] = 2,  and temp < A[j] == true…A[j+1] = A[j], A[1] = A[0], so, after update A = { 2 2 5 3 4}
Finally A = { 2 2 5 3 4}, k = 1

i = 2, temp = 5
j = 1, A[j] = 1, but temp is not less than A[j], so we continue
j = 0, again temp > A[j] so, no problem
A[j+1] = temp = 5, A = { 2 5 5 3 4}

i = 3, temp = 3
j = 2, A[j] = 5, temp < A[j] => A[j+1] = A[j] => A[3] = A[2] => A[3] = 5 and k =2, A={2 5 5 5 4}
j = 1, A[j] = 1, temp > A[j], so no probs
j = 0, A[j] = 1, temp > A[j], so no probs
A[1] = temp = 3, A = {1 1