Python - Count Inversions in an Array

Python – Count Inversions in an Array

Counting inversions in an array is a common problem in data structures and algorithms interviews. An inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j]. This measure tells us how far (or close) the array is from being sorted. In this tutorial, we explain the problem and demonstrate a solution using the efficient merge sort algorithm.

Problem Statement

Given an array arr of size n, count the number of inversions in the array. An inversion is defined as a pair of indices (i, j) where i < j and arr[i] > arr[j].

Sample Input and Output

Example 1:

</>

Copy

# Input array
arr = [2, 4, 1, 3, 5]
# Expected Output: 3
# Explanation:
# Inversions are: (2,1), (4,1), (4,3)

Example 2:

</>

Copy

# Input array
arr = [5, 4, 3, 2, 1]
# Expected Output: 10
# Explanation:
# Every pair is an inversion as the array is in reverse order.

Solution Approach

While a brute-force solution can check every pair and count inversions in O(n²) time, a more efficient approach uses a modified merge sort algorithm. This algorithm counts inversions while sorting the array in O(n log n) time. The main idea is:

Divide the array into two halves.
Recursively count inversions in the left and right halves.
Count the inversions while merging the two sorted halves. When an element from the right half is placed before an element in the left half, it indicates that all remaining elements in the left half form an inversion with that element.
Sum the inversion counts from the left, right, and merge steps to get the total inversion count.

Python Program

The following Python program implements the inversion count using the merge sort approach. Detailed comments are provided to help beginners understand each step.

</>

Copy

def merge(left, right):
    """
    Merge two sorted lists and count inversions.
    An inversion occurs when an element from the right list is placed before an element in the left list.
    """
    merged = []
    i = j = inv_count = 0

    # Merge until one of the lists is exhausted
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            # All remaining elements in left are greater than right[j]
            inv_count += (len(left) - i)
            j += 1

    # Append any remaining elements
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inv_count

def merge_sort(arr):
    """
    Sort the array and count inversions using the merge sort algorithm.
    """
    # Base case: single element or empty array has no inversions
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, inv_left = merge_sort(arr[:mid])
    right, inv_right = merge_sort(arr[mid:])

    merged, inv_split = merge(left, right)
    # Total inversions is the sum from left, right, and during merge
    return merged, inv_left + inv_right + inv_split

# Driver code to test the inversion count function

# Example 1
arr1 = [2, 4, 1, 3, 5]
_, inversion_count1 = merge_sort(arr1)
print("Example 1 - Number of inversions:", inversion_count1)

# Example 2
arr2 = [5, 4, 3, 2, 1]
_, inversion_count2 = merge_sort(arr2)
print("Example 2 - Number of inversions:", inversion_count2)

Conclusion

Counting inversions is a useful problem to understand how modifications to classical algorithms can solve additional tasks. In this tutorial, we covered:

The definition of an inversion and its significance.
Two sets of sample inputs and outputs to illustrate the problem.
A step-by-step explanation of using the merge sort algorithm to count inversions efficiently.
A detailed Python program with comments to help beginners grasp the solution.

This approach is both efficient and widely applicable in interview settings, making it a great problem to master for your DSA interviews.

TutorialKart

Python – Count Inversions in an Array