Counting inversions in an array is a fundamental problem in computer science and programming interviews. This guide will explain what array inversions are, the significance of solving this problem, and different approaches to count inversions of an array in Java.
What are Inversions in an Array?
An inversion in an array is a pair of elements (arr[i], arr[j]) such that:
i < jandarr[i] > arr[j].
For example, in the array [8, 4, 2, 1], there are 6 inversions:
(8, 4),(8, 2),(8, 1),(4, 2),(4, 1),(2, 1).
Counting inversions helps measure how far the array is from being sorted. If the inversion count is zero, the array is already sorted.
Naive Solution Using Two Nested Loops for Count Inversions of an Array
A simple approach involves iterating through the array and counting pairs that satisfy the inversion condition. While easy to understand, this method has a time complexity of O(n2), which is inefficient for large arrays.
Java Code – Naive Solution
public class CountInversionsNaive {
public static int countInversions(int[] arr) {
int count = 0;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] arr = {8, 4, 2, 1};
System.out.println("Number of inversions: " + countInversions(arr));
}
}Complexity:
- Time Complexity: O(n2)
- Space Complexity: O(1)
Efficient Solution Using Merge Sort to Count Inversions of an Array
Merge sort can be modified to count inversions while sorting the array. The algorithm works in O(nlogn)O(n \log n)O(nlogn) time, making it suitable for larger arrays.
How It Works
- Divide: Split the array into two halves recursively.
- Conquer: Count inversions in the left and right halves.
- Combine: Count inversions caused by merging the two halves and merge them in sorted order.
Java Code – Efficient Solution
public class CountInversionsEfficient {
public static int countInversions(int[] arr) {
int[] temp = new int[arr.length];
return mergeSortAndCount(arr, temp, 0, arr.length - 1);
}
private static int mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
int mid, count = 0;
if (left < right) {
mid = (left + right) / 2;
// Count inversions in the left half
count += mergeSortAndCount(arr, temp, left, mid);
// Count inversions in the right half
count += mergeSortAndCount(arr, temp, mid + 1, right);
// Count split inversions and merge the two halves
count += mergeAndCount(arr, temp, left, mid, right);
}
return count;
}
private static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
int i = left; // Starting index for left subarray
int j = mid + 1; // Starting index for right subarray
int k = left; // Starting index to store in temp
int count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
count += (mid - i + 1); // Count inversions
}
}
// Copy remaining elements of left subarray
while (i <= mid) {
temp[k++] = arr[i++];
}
// Copy remaining elements of right subarray
while (j <= right) {
temp[k++] = arr[j++];
}
// Copy temp array back to original array
for (i = left; i <= right; i++) {
arr[i] = temp[i];
}
return count;
}
public static void main(String[] args) {
int[] arr = {8, 4, 2, 1};
System.out.println("Number of inversions: " + countInversions(arr));
}
}Complexity:
- Time Complexity: O(nlogn)
- Space Complexity: O(n)
Applications of Counting Inversions
- Measuring Array Disorder: Inversions indicate how far an array is from being sorted.
- Statistical Analysis: Used in determining similarity between rankings.
- Genomics: Helps in analyzing sequences.
Conclusion
Counting inversions is a classic problem that tests both algorithmic understanding and coding skills. While the naive approach is simple, the merge sort-based method is optimal for large datasets. Mastering this problem not only helps in interviews but also deepens your understanding of sorting algorithms.