Given an array of integers, the task is to count the number of inversions in the array.
In an array, an inversion is a pair of elements (arr[i], arr[j]) such that i < j and arr[i] > arr[j].
Input/Output Examples:
plaintext
Example 1:
Input:
arr = [8, 4, 2, 1]
Output: 6
Explanation: There are 6 inversions in the array: (8, 4), (8, 2), (8, 1), (4, 2), (4, 1), and (2, 1).
Example 2:
Input:
arr = [3, 1, 2]
Output: 2
Explanation: There are 2 inversions in the array: (3, 1) and (3, 2).
Example 3:
Input:
arr = [1, 2, 3, 4]
Output: 0
Explanation: The array is already sorted, so there are no inversions.
Approach to count the number of inversions in an array
- Use a Modified Merge Sort:
- Inversions can be counted efficiently using a modified merge sort algorithm. During the merge step, count the number of inversions for each split pair.
- Count Inversions During Merge:
- While merging two halves, if
left[i] > right[j], then all remaining elements in the left half (fromionward) are greater thanright[j], and this counts as inversions.
- While merging two halves, if
- Recursively Sort and Count:
- Recursively sort the array while counting the inversions. Each merge operation contributes to the overall count of inversions.
C++ Program to count the number of inversions in an array
cpp
#include <iostream>
#include <vector>
using namespace std;
// Function to merge two halves and count inversions
int mergeAndCount(vector<int>& arr, vector<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 be sorted
int inversions = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
inversions += (mid - i + 1);
}
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inversions;
}
// Function to recursively sort and count inversions
int mergeSortAndCount(vector<int>& arr, vector<int>& temp, int left, int right) {
int inversions = 0;
if (left < right) {
int mid = (left + right) / 2;
inversions += mergeSortAndCount(arr, temp, left, mid);
inversions += mergeSortAndCount(arr, temp, mid + 1, right);
inversions += mergeAndCount(arr, temp, left, mid, right);
}
return inversions;
}
// Function to count inversions in the array
int countInversions(vector<int>& arr) {
vector<int> temp(arr.size());
return mergeSortAndCount(arr, temp, 0, arr.size() - 1);
}
int main() {
vector<int> arr = {8, 4, 2, 1};
cout << "Number of inversions: " << countInversions(arr) << endl;
return 0;
}
Java Program to count the number of inversions in an array
java
public class InversionCount {
// Function to merge two halves and count inversions
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 be sorted
int inversions = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
inversions += (mid - i + 1);
}
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inversions;
}
// Function to recursively sort and count inversions
private static int mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
int inversions = 0;
if (left < right) {
int mid = (left + right) / 2;
inversions += mergeSortAndCount(arr, temp, left, mid);
inversions += mergeSortAndCount(arr, temp, mid + 1, right);
inversions += mergeAndCount(arr, temp, left, mid, right);
}
return inversions;
}
// Function to count inversions in the array
public static int countInversions(int[] arr) {
int[] temp = new int[arr.length];
return mergeSortAndCount(arr, temp, 0, arr.length - 1);
}
public static void main(String[] args) {
int[] arr = {8, 4, 2, 1};
System.out.println("Number of inversions: " + countInversions(arr));
}
}
Python Program to count the number of inversions in an array
python
# Function to merge two halves and count inversions
def merge_and_count(arr, temp, left, mid, right):
i = left # Starting index for left subarray
j = mid + 1 # Starting index for right subarray
k = left # Starting index to be sorted
inversions = 0
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp[k] = arr[i]
i += 1
else:
temp[k] = arr[j]
inversions += (mid - i + 1)
j += 1
k += 1
while i <= mid:
temp[k] = arr[i]
i += 1
k += 1
while j <= right:
temp[k] = arr[j]
j += 1
k += 1
for i in range(left, right + 1):
arr[i] = temp[i]
return inversions
# Function to recursively sort and count inversions
def merge_sort_and_count(arr, temp, left, right):
inversions = 0
if left < right:
mid = (left + right) // 2
inversions += merge_sort_and_count(arr, temp, left, mid)
inversions += merge_sort_and_count(arr, temp, mid + 1, right)
inversions += merge_and_count(arr, temp, left, mid, right)
return inversions
# Function to count inversions in the array
def count_inversions(arr):
temp = [0] * len(arr)
return merge_sort_and_count(arr, temp, 0, len(arr) - 1)
# Example usage
if __name__ == "__main__":
arr = [8, 4, 2, 1]
print("Number of inversions:", count_inversions(arr))
Time Complexity
- O(n log n): The modified merge sort algorithm has a time complexity of O(n log n) due to the recursive splitting and merging steps.
Space Complexity
- O(n): Additional space is needed for the temporary array used during merging.