Geeksforgeeks: Count Inversions

 Count Inversions

Difficulty: Medium

Given an array of integers arr[]. Find the Inversion Count in the array.
Two elements arr[i] and arr[j] form an inversion if arr[i] > arr[j] and i < j.

Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0.
If an array is sorted in the reverse order then the inversion count is the maximum. 

Examples:

Input: arr[] = [2, 4, 1, 3, 5]
Output: 3
Explanation: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

Input: arr[] = [2, 3, 4, 5, 6]
Output: 0
Explanation: As the sequence is already sorted so there is no inversion count.

Input: arr[] = [10, 10, 10]
Output: 0
Explanation: As all the elements of array are same, so there is no inversion count.

Constraints:
1 ≤ arr.size() ≤ 105
1 ≤ arr[i] ≤ 104

The Inversion Count is a key concept in analyzing the sortedness of an array. An inversion is a pair of elements in the array such that the first element is greater than the second one, and the first element appears before the second one in the array.

We can approach the problem using different methods, from brute force to optimized solutions leveraging sorting algorithms. Below are several approaches to solve this problem:

Approach 1: Brute Force Approach

This approach involves checking every possible pair (i, j) where i < j. If arr[i] > arr[j], we count that pair as an inversion.

Code for Brute Force:

using System;

public class Solution {
    public int InversionCount(int[] arr) {
        int count = 0;
        int n = arr.Length;

        // Check every pair of elements
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();

        int[] arr1 = { 2, 4, 1, 3, 5 };
        Console.WriteLine(solution.InversionCount(arr1));  // Output: 3

        int[] arr2 = { 2, 3, 4, 5, 6 };
        Console.WriteLine(solution.InversionCount(arr2));  // Output: 0

        int[] arr3 = { 10, 10, 10 };
        Console.WriteLine(solution.InversionCount(arr3));  // Output: 0
    }
}

Time Complexity:

• Time Complexity: $O(n^2)$, where n is the length of the array. This is because we are using two nested loops to check all pairs of elements.
• Space Complexity: $O(1)$, as we are using a constant amount of extra space.

---

Approach 2: Optimized Approach Using Modified Merge Sort

Merge Sort can be modified to count inversions during the merge step. The idea is that when merging two sorted halves of the array, every time we find an element in the right half that is smaller than an element in the left half, we have found an inversion. The number of such inversions can be determined by how many elements are remaining in the left half (because all those elements are greater than the current element of the right half).

Code for Merge Sort Approach:

using System;

public class Solution {
    public int MergeAndCount(int[] arr, int left, int mid, int right) {
        int count = 0;
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        Array.Copy(arr, left, leftArr, 0, n1);
        Array.Copy(arr, mid + 1, rightArr, 0, n2);

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
                count += (n1 - i);  // All remaining elements in leftArr are greater than rightArr[j]
            }
        }

        while (i < n1) {
            arr[k++] = leftArr[i++];
        }

        while (j < n2) {
            arr[k++] = rightArr[j++];
        }

        return count;
    }

    public int InversionCount(int[] arr, int left, int right) {
        int count = 0;
        if (left < right) {
            int mid = left + (right - left) / 2;

            // Recursively count inversions in the left and right subarrays
            count += InversionCount(arr, left, mid);
            count += InversionCount(arr, mid + 1, right);

            // Count inversions during the merge step
            count += MergeAndCount(arr, left, mid, right);
        }
        return count;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();

        int[] arr1 = { 2, 4, 1, 3, 5 };
        Console.WriteLine(solution.InversionCount(arr1, 0, arr1.Length - 1));  // Output: 3

        int[] arr2 = { 2, 3, 4, 5, 6 };
        Console.WriteLine(solution.InversionCount(arr2, 0, arr2.Length - 1));  // Output: 0

        int[] arr3 = { 10, 10, 10 };
        Console.WriteLine(solution.InversionCount(arr3, 0, arr3.Length - 1));  // Output: 0
    }
}

Time Complexity:

• Time Complexity: $O(n \log n)$, where n is the length of the array. The merge sort algorithm divides the array into two halves, and the merging step takes linear time.
• Space Complexity: $O(n)$, since we need extra space for the temporary arrays used during merging.

---

Approach 3: Using Binary Indexed Tree (BIT) or Fenwick Tree

This is a more advanced approach where we maintain a Binary Indexed Tree (BIT) to keep track of the counts of elements while iterating over the array. For each element in the array, we can query the BIT to get the number of elements that are greater than the current element and appear before it in the array.

Steps:

1. Traverse the array from right to left.
2. For each element arr[i], use the BIT to query how many elements are smaller than arr[i] and update the BIT for arr[i].

This approach is efficient but requires additional data structures.

---

Conclusion

1. Brute Force: Simple but inefficient for large arrays with $O(n^2)$ complexity.
2. Merge Sort: Efficient with $O(n \log n)$ complexity, using a modified merge step to count inversions.
3. Binary Indexed Tree: More advanced, efficient $O(n \log m)$, where $m$ is the maximum element in the array, and uses BIT for querying and updating counts.

For most practical purposes, Merge Sort is the go-to solution due to its balance of simplicity and efficiency.