Count Inversions in an array in Java
Counting inversions in an array is a problem in computer science that involves finding the number of pairs of elements in an array that are out of order with respect to each other. In other words, if an array is given, the problem is to find the number of pairs of elements such that the left element is greater than the right element, but their positions in the array are in the opposite order.
Example 1:
Input: [2, 4, 1, 3, 5]
Output: 3
Explanation: The three inversions are (2, 1), (4, 1), and (4, 3).
Example 2:
Input: [5, 4, 3, 2, 1]
Output: 10
Explanation: The ten inversions are (5, 4), (5, 3), (5, 2), (5, 1), (4, 3), (4, 2), (4, 1), (3, 2), (3, 1), and (2, 1).
Example 3:
Input: [1, 2, 3, 4, 5]
Output: 0
Explanation: There are no inversions in this array.
Example 4:
Input: [1, 3, 2, 4, 5]
Output: 1
Explanation: The only inversion is (3, 2).
Example 5:
Input: [1, 5, 3, 2, 4]
Output: 4
Explanation: The four inversions are (5, 3), (5, 2), (5, 4), and (3, 2).
Approach: Using Brute Force
ALGORITHM:
- Initialize a variable count to 0.
- Loop through each pair of elements in the array.
- If the left element is greater than the right element, increment the count by 1.
- Return the count as the number of inversions in the array.
File Name: CountInversions.java
import java.util.*;
public class CountInversions {
public static void main(String[] args) {
// Take input array from user
Scanner sc = new Scanner(System.in);
System.out.println("Enter the elements of the array separated by space:");
String[] input = sc.nextLine().split(" ");
int[] arr = new int[input.length];
for (int i = 0; i < input.length; i++) {
arr[i] = Integer.parseInt(input[i]);
}
// Call the countInversions function and print the result
int count = countInversions(arr);
System.out.println("Number of inversions: " + count);
}
// Function to count inversions using brute force
public static int countInversions(int[] arr) {
int n = arr.length;
int count = 0;
// Compare each pair of elements
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
}
Output:
Enter the elements of the array separated by space:
2 4 1 3 5
Number of inversions: 3
Enter the elements of the array separated by space:
5 4 3 2 1
Number of inversions: 10
Enter the elements of the array separated by space:
1 2 3 4 5
Number of inversions: 0
Enter the elements of the array separated by space:
1 3 2 4 5
Number of inversions: 1
Enter the elements of the array separated by space:
1 5 3 2 4
Number of inversions: 4
Explanation:
In this implementation, we first take the input array from the user, convert it to an integer array, and then call the countInversions
function. The countInversions
function uses a nested loop to compare each pair of elements in the array and increment a counter variable whenever a pair of elements is out of order. Finally, the function returns the count of inversions.
Complexity Analysis:
The time complexity of the brute force approach to count inversions in an array in Java is O(n^2), where n is the length of the array. Here the algorithm involves comparing each pair of elements in the array, which takes O(n^2) time in the worst case.
The space complexity of the algorithm is O(1), since it only uses a constant amount of additional space to store the count variable.
Approach: Using MergeSort
FileName: InversionCount.java
public class InversionCount {
// Merge sort function to count inversions
public static int mergeSort(int[] arr) {
if (arr.length < 2) {
return 0;
}
int[] temp = new int[arr.length]; // Temporary array to store sorted elements
return mergeSort(arr, temp, 0, arr.length - 1);
}
// Recursive helper function for merge sort
private static int mergeSort(int[] arr, int[] temp, int left, int right) {
if (left == right) { // Base case: one element in array
return 0;
}
int mid = (left + right) / 2; // Calculate midpoint index
int count = 0;
count += mergeSort(arr, temp, left, mid); // Recursively sort left half of array
count += mergeSort(arr, temp, mid + 1, right); // Recursively sort right half of array
count += merge(arr, temp, left, mid + 1, right); // Merge left and right halves together
return count;
}
// Merge function to combine two sorted halves of an array and count inversions
private static int merge(int[] arr, int[] temp, int left, int mid, int right) {
int i = left, j = mid, k = left;
int count = 0;
while (i <= mid - 1 && j <= right) { // Merge left and right halves of array
if (arr[i] <= arr[j]) { // If left element is smaller than right element
temp[k++] = arr[i++]; // Copy left element to temporary array
} else { // If right element is smaller than left element
temp[k++] = arr[j++]; // Copy right element to temporary array
count += mid - i; // Count inversions
}
}
while (i <= mid - 1) { // Copy remaining elements from left half of array
temp[k++] = arr[i++];
}
while (j <= right) { // Copy remaining elements from right half of array
temp[k++] = arr[j++];
}
for (i = left; i <= right; i++) { // Copy sorted elements back into original array
arr[i] = temp[i];
}
return count; // Return number of inversions encountered
}
public static void main(String[] args) {
int[] arr = { 2, 4, 1, 3, 5 };
int count = mergeSort(arr); // Count inversions in array using merge sort
System.out.println("Number of inversions: " + count); // Print number of inversions
int[] arr2 = { 1, 2, 3, 4, 5 };
int count2 = mergeSort(arr2); // Count inversions in sorted array
System.out.println("Number of inversions: " + count2); // Print number of inversions (should be 0)
int[] arr3 = { 5, 4, 3, 2, 1 };
int count3 = mergeSort(arr3); // Count inversions in reverse sorted array
System.out.println("Number of inversions: " + count3); // Print number of inversions (should be 10)
}
}
Output:
Number of inversions: 3
Number of inversions: 0
Number of inversions: 10
Complexity Analysis:
Time complexity: The time complexity of the Merge Sort algorithm used to count inversions is O(n log n), where n is the size of the input array. The merge function takes O(n) time to merge the two sub-arrays, resulting in a total time complexity of O(n log n).
Space complexity: The space complexity of the Merge Sort algorithm used to count inversions is O(n), where n is the size of the input array. The space complexity is proportional to the size of the input array.
Approach: Using Self Balanced Tree
FileName: InversionCount.java
import java.util.*;
public class InversionCount {
// Node class to represent a node in the binary search tree
static class Node {
int value, leftCount; // value of node and number of nodes in its left subtree
Node left, right; // left and right children of the node
public Node(int value) {
this.value = value;
this.leftCount = 0;
this.left = null;
this.right = null;
}
}
// Tree class to represent the binary search tree
static class Tree {
Node root; // root of the tree
// insert a value into the tree
public void insert(int value) {
root = insert(root, value);
}
// insert a value into a node in the tree
private Node insert(Node node, int value) {
if (node == null) {
// if the node is null, create a new node with the given value
return new Node(value);
}
if (value <= node.value) {
// if the value is less than or equal to the current node's value,
// insert the value into the left subtree and increment the leftCount
node.leftCount++;
node.left = insert(node.left, value);
} else {
// if the value is greater than the current node's value,
// insert the value into the right subtree
node.right = insert(node.right, value);
}
return node;
}
// count the number of inversions for a given value
public int countInversions(int value) {
return countInversions(root, value);
}
// count the number of inversions for a given value starting from a given node
private int countInversions(Node node, int value) {
if (node == null) {
// if the node is null, there are no inversions
return 0;
}
if (value <= node.value) {
// if the value is less than or equal to the current node's value,
// count the inversions in the left subtree
return countInversions(node.left, value);
} else {
// if the value is greater than the current node's value,
// count the inversions in the right subtree and add the leftCount of the current node
// and 1 to account for the current node itself
return node.leftCount + 1 + countInversions(node.right, value);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the elements of the array separated by space:");
String[] input = sc.nextLine().split(" ");
int[] arr = new int[input.length];
for (int i = 0; i < input.length; i++) {
arr[i] = Integer.parseInt(input[i]);
}
Tree tree = new Tree();
int count = 0;
for (int i = 0; i < arr.length; i++) {
// count the number of inversions for the current element in the array
// and add it to the total count
count += i - tree.countInversions(arr[i]);
// insert the current element into the tree
tree.insert(arr[i]);
}
System.out.println("Number of inversions: " + count);
}
}
Explanation:
The implementation uses a self-balancing tree (in this case, a binary search tree) to count the number of inversions in an array. The tree is constructed by inserting each element in the array one at a time. As each element is inserted, the number of inversions it creates is counted by finding the number of elements that have already been inserted that are greater than the current element. This count is added to a running total, which is returned as the final result.
Output:
Enter the elements of the array separated by space:
2 4 1 3 5
Number of inversions: 3
Enter the elements of the array separated by space:
1 2 3 4 5
Number of inversions: 0
Enter the elements of the array separated by space:
5 4 3 2 1
Number of inversions: 10
Approach: Using Binary Indexed Tree
FileName: BIT.java
import java.util.*;
class BIT {
int[] tree;
int size;
public BIT(int n) {
size = n;
tree = new int[n + 1];
}
// Update BIT for a given index i with a given value val
public void update(int i, int val) {
while (i <= size) {
tree[i] += val;
i += (i & -i);
}
}
// Get the prefix sum up to index i
public int getPrefixSum(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= (i & -i);
}
return sum;
}
}
public class CountInversionsBIT {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Take input for size of array
int n = sc.nextInt();
// Take input for array elements
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// Create a copy of the input array and sort it
int[] sortedArr = Arrays.copyOf(arr, n);
Arrays.sort(sortedArr);
// Create a map of the values in the sorted array to their positions
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(sortedArr[i], i + 1);
}
// Create a Binary Indexed Tree with size n
BIT bit = new BIT(n);
// Initialize inversion count to 0
long invCount = 0;
// Traverse the original array from right to left
for (int i = n - 1; i >= 0; i--) {
// Get the position of the current element in the sorted array
int pos = map.get(arr[i]);
// Get the prefix sum up to position pos-1
int prefixSum = bit.getPrefixSum(pos - 1);
// Add the prefix sum to the inversion count
invCount += prefixSum;
// Update the Binary Indexed Tree for the current position
bit.update(pos, 1);
}
// Output the inversion count
System.out.println("Number of inversions: " + invCount);
}
}
Output:
5
2 4 1 3 5
Number of inversions: 3
5
5 4 3 2 1
Number of inversions: 10
5
1 2 3 4 5
Number of inversions: 0
Complexity Analysis:
Time complexity of the Count Inversions using Binary Indexed Tree algorithm is O(n log n), where n is the size of the input array. Here the algorithm involves sorting the input array, which takes O(n log n) time, and then performing n updates on the Binary Indexed Tree, each of which takes O(log n) time.
The space complexity of the algorithm is O(n), as it involves creating an additional copy of the input array and a Binary Indexed Tree of size n.