ArrayProblem 16 of 36
Count Inversion
Problem Statement
Given an array of integers, count the number of inversions in it. Two elements arr[i] and arr[j] form an inversion if arr[i] > arr[j] and i < j.
Example:
- Input:
[2, 4, 1, 3, 5] - Output:
3 - Explanation: Inversions are
(2,1),(4,1),(4,3)
Approach 1: Brute Force
Intuition
Check all pairs (i, j) where i < j and count pairs where arr[i] > arr[j].
Algorithm
- Use two nested loops
- For each pair
(i, j)wherei < j - If
arr[i] > arr[j], increment count
java
public class Solution {
public long countInversionsBruteForce(int[] arr) {
int n = arr.length;
long count = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
}Complexity Analysis
- Time Complexity: O(n²) - Checking all pairs
- Space Complexity: O(1) - No extra space used
Approach 2: Modified Merge Sort (Optimal)
Intuition
During merge sort, when merging two sorted halves, if an element from the right half is smaller than an element from the left half, it forms inversions with all remaining elements in the left half.
Algorithm
- Divide the array into two halves
- Recursively count inversions in each half
- Count inversions during the merge step
- When
left[i] > right[j], add(mid - i + 1)to count
java
public class Solution {
private long merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
long inversions = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
// All elements from i to mid are greater than arr[j]
temp[k++] = arr[j++];
inversions += (mid - i + 1);
}
}
// Copy remaining elements
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// Copy back to original array
for (int m = left; m <= right; m++) {
arr[m] = temp[m - left];
}
return inversions;
}
private long mergeSort(int[] arr, int left, int right) {
long inversions = 0;
if (left < right) {
int mid = left + (right - left) / 2;
// Count inversions in left half
inversions += mergeSort(arr, left, mid);
// Count inversions in right half
inversions += mergeSort(arr, mid + 1, right);
// Count split inversions during merge
inversions += merge(arr, left, mid, right);
}
return inversions;
}
public long countInversions(int[] arr) {
return mergeSort(arr, 0, arr.length - 1);
}
}Complexity Analysis
- Time Complexity: O(n log n) - Same as merge sort
- Space Complexity: O(n) - Temporary array for merging
Visual Example
For array [2, 4, 1, 3, 5]:
Initial: [2, 4, 1, 3, 5]
Divide:
[2, 4] and [1, 3, 5]
Further divide:
[2] [4] and [1] [3, 5]
[3] [5]
Merge [3, 5]: No inversions (3 < 5)
Result: [3, 5]
Merge [1] and [3, 5]:
1 < 3: pick 1
Result: [1, 3, 5], inversions = 0
Merge [2] and [4]:
2 < 4: pick 2
Result: [2, 4], inversions = 0
Merge [2, 4] and [1, 3, 5]:
1 < 2: pick 1, inversions += 2 (2 and 4 > 1)
2 < 3: pick 2
3 < 4: pick 3, inversions += 1 (4 > 3)
4 < 5: pick 4
pick 5
Result: [1, 2, 3, 4, 5], inversions = 3
Total inversions = 3
Key Takeaways
- Inversions measure sortedness - A sorted array has 0 inversions; reverse sorted has n(n-1)/2
- Divide and conquer efficiently counts inversions
- Split inversions are counted during the merge step
- When
left[i] > right[j], all elements fromitomidform inversions withright[j] - This technique is useful in problems involving pairs with ordering constraints
- Applications: Measuring similarity between rankings, counting swaps in bubble sort