Table of contents

Count number of Inversions in an array

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

  1. 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.
  2. Count Inversions During Merge:
    • While merging two halves, if left[i] > right[j], then all remaining elements in the left half (from i onward) are greater than right[j], and this counts as inversions.
  3. 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.

DSA

Related Articles