Count Inversions of an Array

Difficulty: Medium, Asked In Microsoft, Amazon, Adobe.

Key takeaway: An excellent problem to learn problem-solving using the divide and conquer idea similar to the merge sort.

Let’s understand the problem

Given an array of n integers X[], write a program to find the total number of inversion counts in X[]. An inversion occurs when there are two elements in the array such that i < j and X[i] > X[j]. In this situation, the pair (i, j) is called an inversion and the inversion count is the count of such inversions present in the array.

Problem Note

The inversion count indicates how close the array is to being sorted. If the array is sorted in increasing order, the inversion count is 0. If the array is sorted in reverse order, the inversion count is at its maximum.
Assume that all elements are unique.
Before attempting to solve this problem, we highly recommend learning or revising the idea of the divide and conquer approach and the merge sort algorithm.

Examples

Input: X[] = [5, 2, 6, 3] Output: 3

Explanation: There are 3 inversions: (5, 2), (5, 3), and (6, 3).

Input: X[] = [3, 2, 1] Output: 3

Explanation: There are 3 inversions: (3, 2), (3, 1), and (2, 1).

Input: X[] = [1, 2, 3] Output: 0

Explanation: The array is already sorted in increasing order, so there are no inversions.

Discussed Solution Approaches

Brute force approach using nested loops
Brute force approach using divide and conquer approach
Efficient divide and conquer approach using merge sort

Brute force approach using nested loops

Solution idea

One basic idea is to traverse the array and find the inversion count for every element. To do this, we count the number of smaller elements on its right side. During this process, we also keep adding the inversion count for each element to get the overall inversion count.

Solution steps

We can implement the above idea using two nested loops.

We Initialize a variable invCount to track the total inversion count.
Now we traverse the array from i = 0 to n - 2 using the outer loop. For each element, X[i], we find the count of elements smaller than X[i] on the right side (j = i + 1 to n - 1) using an inner loop. We track this count using the variable smallerCount.
By the end of the inner loop, we add smallerCount to invCount.
By the end of the outer loop, we return invCount.

Solution pseudocode

countInversions(X, n)
    inversionCount = 0
    for i from 0 to n - 2
        smallerCount = 0
        for j from i + 1 to n - 1
            if X[j] < X[i]
                smallerCount = smallerCount + 1

        inversionCount = inversionCount + smallerCount

    return inversionCount

Another implementation using nested loops

The idea is to compare each pair of elements (X[i] and X[j] where i < j). If the element at index i is greater than the element at index j, it indicates an inversion. So, we increase the inversion count by one.

countInversions(X, n)
    inversionCount = 0
    for i from 0 to n - 2
        for j from i + 1 to n - 1
            if X[i] > X[j]
                inversionCount = inversionCount + 1

    return inversionCount

Time and space complexity analysis

We are using two nested loops and performing an O(1) operation at each iteration. Total number of loop iterations = (n - 1) + (n - 2) + … + 2 + 1 = n(n - 1)/2. So time complexity = O(n²). As we are using constant extra space, the space complexity = O(1).

Brute force approach using divide and conquer

Solution idea

In this approach, we divide the unsorted array into two equal halves and recursively find the inversion count of the first half (invCountLeft) and the inversion count of the second half (invCountRight). The total inversion count up to this point is equal to invCountLeft + invCountRight.

To calculate the overall inversion count, we need to consider an extra scenario: the type of inversion where one element is in the left part and another element is in the right part (invCountCrossing). To find this, we traverse the left half and for each element x in the left half, we count all elements y in the right half that are less than x. This operation takes O(n²) time because both arrays have a size of n/2.

Total inversion count = invCountLeft + invCountRight + invCountCrossing.

Solution pseudocode

countCrossingInversions(X, left, mid, right)
    inversionCount = 0
    for i from left to mid
        for j from mid + 1 to right
            if X[i] > X[j]
                inversionCount = inversionCount + 1

    return inversionCount


findInversionCount(X, left, right)
    if left >= right
        return 0

    mid = left + (right - left) / 2

    leftCount = findInversionCount(X, left, mid)
    rightCount = findInversionCount(X, mid + 1, right)
    crossingCount = countCrossingInversions(X, left, mid, right)

    return leftCount + rightCount + crossingCount


countInversions(X, n)
    if n == 0
        return 0

    return findInversionCount(X, 0, n - 1)

Time and space complexity analysis

We are solving the problem of size n by recursively solving the two sub-problems of size n/2 and performing extra O(n²) operations to find invCountCrossing. So the recurrence relation for time complexity is T(n) = 2T(n/2) + O(n^2), which is a divide-and-conquer recurrence. We can apply the master theorem to solve it. Note: If you want to learn about recursion analysis, explore this blog: Analysis of recursion.

Master theorem

If T(n) = aT(n/b) + O(n^k), where a ≥ 1 and b > 1, there are three cases of the master theorem:

If k < logb(a): T(n) = O(n^logb(a))
If k = logb(a): T(n) = O((n^k) * logn)
If k > logb(a): T(n) = O(n^k)

Comparing the given recurrence T(n) = 2T(n/2) + O(n^2) with the master theorem recurrence:

T(n) = 2T(n/2) + O(n^2)
T(n) = aT(n/b) + O(n^k)

Here, a = 2, b = 2, and k = 2 => logb(a) = log2(2) = 1. Since k > logb(a), it satisfies the third case of the master theorem. So the time complexity = O(n^k) = O(n^2). There is no improvement in time complexity compared to the previous approach!

The space complexity depends on the size of the recursion call stack, which is equal to the maximum depth of the recursion tree. Since the input parameters decrease by a factor of 2, the maximum depth of the recursion tree is O(logn). So, the space complexity is O(logn).

Efficient divide and conquer approach using merge sort

Solution idea

This is an interesting approach that leverages the idea of merge sort to optimize the previous divide and conquer approach. The critical question is: What is the thought process behind this idea? Let's think!

The previous divide and conquer approach does not work well because its time complexity is O(n²). This is primarily due to the time-consuming process of counting inversions across the two halves. Can we think of a way to optimize this approach?

Consider the following scenario: After finding the inversion count of both the left and right halves, suppose both halves also get sorted in increasing order. Now, sorting will help us to easily count the inversions across the two halves in O(n) time. The idea is simple: since both halves are sorted, we can use a two-pointer merging process similar to merge sort!

If we observe, this idea aligns closely with the merge sort, with a slight modification:

Recursive calls to both halves in merge sort will help us find the inversion count of each half. The advantage is that both halves will also become sorted after recursive calls.
The merging process in merge sort will also help in identifying the inversion count across the two halves.

Solution steps

Divide the array into two halves.
Recursively sort each half and calculate the inversion counts.
Merge the sorted halves together, while also tracking the inversion count across both halves.
Return the total inversion count, which is the sum of the inversion counts in the first half, the second half, and the inversions during the merging process.

Inversion count solution using merge sort

Solution pseudocode

mergeSort(X, left, right)
    leftInversions = 0
    rightInversions = 0
    crossingInversions = 0

    if left < right
        mid = left + (right - left) / 2

        leftInversions = mergeSort(X, left, mid)
        rightInversions = mergeSort(X, mid + 1, right)
        crossingInversions = merge(X, left, mid, right)

    return leftInversions + rightInversions + crossingInversions

Implementation of merge function: Counting inversion count crossing both halves

During the merge process, we can find the inversion count using two-pointers approach.

Suppose the size of the left and right halves are n1 and n2. Here n1 = mid - l + 1 and n2 = r - mid. Now, following the merging process of merge sort, we create two auxiliary memory spaces, A[n1] and B[n2], to store copies of both sorted halves.

Now we initialize two pointers, i and j, to traverse the first and second sorted halves. We traverse sorted halves simultaneously using a loop condition: while (i < n1 && j < n2).

If A[i] > B[j], it is an inversion. Since the left and right subarrays are sorted, there are (n1 - i) inversions. The reason is simple: All the remaining elements in the left subarray (A[i+1], A[i+2], ..., A[n1-1]) will also be greater than B[j].
If A[i] ≤ B[j], there is no inversion. The remaining steps are similar to the merging process of merge sort.

Counting inversion during merge process of merge sort algorithm

merge(X, l, mid, r)
    n1 = mid - l + 1
    n2 = r - mid
    inversionCount = 0

    A = copy X[l ... mid]
    B = copy X[mid + 1 ... r]

    i = 0, j = 0, k = l
    while i < n1 and j < n2
        if A[i] > B[j]
            X[k] = B[j]
            j = j + 1
            // A[i ... n1 - 1] are all greater than B[j - 1]
            inversionCount = inversionCount + (n1 - i)
        else
            X[k] = A[i]
            i = i + 1

        k = k + 1

    while i < n1
        X[k] = A[i]
        i = i + 1
        k = k + 1

    while j < n2
        X[k] = B[j]
        j = j + 1
        k = k + 1

    return inversionCount

Time and space complexity analysis

The time and space complexity of this approach is the same as the time complexity of the merge sort algorithm. Time complexity = O(nlogn), space complexity = O(n).

Critical ideas to think!

Can we solve this problem using a hash table, binary search tree, or segment tree?
During the merge process, if A[i] > B[j], why do we increment the inversion count by n1 - i?
Can we consider solving this problem using the insertion sort or bubble sort algorithm?
If there are O(n) inversions in the array, what would be the time complexity of the insertion sort algorithm?
What approach should we take if we need to count the inversion count for every element?

Inversion Count in an Array

Let’s understand the problem

Problem Note

Examples

Discussed Solution Approaches

Brute force approach using nested loops

Solution idea

Solution steps

Solution pseudocode

Another implementation using nested loops

Time and space complexity analysis

Brute force approach using divide and conquer

Solution idea

Solution pseudocode

Time and space complexity analysis

Efficient divide and conquer approach using merge sort

Solution idea

Solution steps

Solution pseudocode

Implementation of merge function: Counting inversion count crossing both halves

Time and space complexity analysis

Critical ideas to think!

Similar coding questions to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs