Count Inversions

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() ≤ 10⁵
1 ≤ arr[i] ≤ 10⁴

Approach 01:

class Solution {
public:
    int inversionCount(vector<int>& arr) {
        auto fenwickUpdate = [](vector<int>& fenwickTree, int index, int delta, int maxValue) {
            while (index <= maxValue) {
                fenwickTree[index] += delta;
                index += index & -index;
            }
        };

        auto fenwickSum = [](vector<int>& fenwickTree, int index) {
            int total = 0;
            while (index > 0) {
                total += fenwickTree[index];
                index -= index & -index;
            }
            return total;
        };

        int arraySize = arr.size();
        int maxValue = *max_element(arr.begin(), arr.end());

        // Create a Fenwick Tree of size maxValue + 1
        vector<int> fenwickTree(maxValue + 1, 0);

        // Start from the rightmost element to count inversions
        int inversionCount = 0;
        for (int currentIndex = arraySize - 1; currentIndex >= 0; currentIndex--) {
            // Count elements smaller than arr[currentIndex]
            inversionCount += fenwickSum(fenwickTree, arr[currentIndex] - 1);

            // Update the Fenwick Tree with the current element
            fenwickUpdate(fenwickTree, arr[currentIndex], 1, maxValue);
        }

        return inversionCount;
    }
};

class Solution:
    def inversionCount(self, arr):
        def fenwickUpdate(fenwickTree, index, delta, maxValue):
            while index <= maxValue:
                fenwickTree[index] += delta
                index += index & -index

        def fenwickSum(fenwickTree, index):
            total = 0
            while index > 0:
                total += fenwickTree[index]
                index -= index & -index
            return total

        arraySize = len(arr)
        maxValue = max(arr)

        # Create a Fenwick Tree of size maxValue + 1
        fenwickTree = [0] * (maxValue + 1)

        # Start from the rightmost element to count inversions
        inversionCount = 0
        for currentIndex in range(arraySize - 1, -1, -1):
            # Count elements smaller than arr[currentIndex]
            inversionCount += fenwickSum(fenwickTree, arr[currentIndex] - 1)

            # Update the Fenwick Tree with the current element
            fenwickUpdate(fenwickTree, arr[currentIndex], 1, maxValue)

        return inversionCount

Time Complexity

• Initialization:

  Finding the maximum value in the array (`maxValue`) using max_element takes \(O(n)\), where \(n\) is the size of the input array arr.

• Processing each element:
  • Each iteration of the loop performs two key operations:
    • fenwickSum, which computes the prefix sum in a Fenwick Tree. This takes \(O(\log(\text{maxValue}))\) per call.
    • fenwickUpdate, which updates the Fenwick Tree. This also takes \(O(\log(\text{maxValue}))\) per call.
  • Since the loop runs \(n\) times, these operations collectively contribute \(O(n \cdot \log(\text{maxValue}))\).
• Overall Time Complexity:

  The total time complexity is \(O(n + n \cdot \log(\text{maxValue}))\), where \(n\) is the size of the array, and \(\text{maxValue}\) is the largest element in the array. The \(O(n)\) term comes from initialization, while \(O(n \cdot \log(\text{maxValue}))\) dominates for large inputs.

Space Complexity

• Fenwick Tree:

  The Fenwick Tree is a vector of size \(\text{maxValue} + 1\), requiring \(O(\text{maxValue})\) space.

• Auxiliary variables:

  The function uses a few integer variables and lambdas, which require \(O(1)\) space.

• Overall Space Complexity:

  The total space complexity is \(O(\text{maxValue})\).