Count Inversions in Array in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Count inversions in a small array

What is the output of the following code that counts inversions in the array?

DSA Python

def count_inversions(arr):
    inv_count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                inv_count += 1
    return inv_count

print(count_inversions([2, 4, 1, 3, 5]))

A 4

B 3

C 2

D 5

💡 Hint

Count pairs where a bigger number appears before a smaller number.

The pairs are (2,1), (4,1), and (4,3), so total 3 inversions.

❓ Predict Output

intermediate

Count inversions using merge sort method

What is the output of this code that counts inversions using merge sort?

DSA Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, left_inv = merge_sort(arr[:mid])
    right, right_inv = merge_sort(arr[mid:])
    merged, split_inv = merge(left, right)
    return merged, left_inv + right_inv + split_inv

def merge(left, right):
    i = j = 0
    merged = []
    inv_count = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inv_count += len(left) - i
            j += 1
    merged += left[i:]
    merged += right[j:]
    return merged, inv_count

arr = [8, 4, 2, 1]
_, result = merge_sort(arr)
print(result)

A 6

B 5

C 4

D 7

💡 Hint

Merge sort counts split inversions when right element is smaller.

The array has 6 inversions: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1).

🔧 Debug

advanced

Identify the error in inversion count code

What error does this code raise when run?

DSA Python

def count_inversions(arr):
    inv_count = 0
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] > arr[j]:
                inv_count += 1
    return inv_count

print(count_inversions(None))

A NameError: name 'inv_count' is not defined

B IndexError: list index out of range

C TypeError: object of type 'NoneType' has no len()

D No error, output is 0

💡 Hint

Check what happens if input is None instead of a list.

Calling len(None) causes TypeError because NoneType has no length.

🚀 Application

advanced

Find number of inversions after swapping two elements

Given the array [3, 1, 2, 5, 4], if we swap elements at indices 1 and 4, what is the new inversion count?

A 6

B 5

C 3

D 2

💡 Hint

Count inversions before and after swap carefully.

Original inversions: (3,1), (3,2), (5,4) = 3. After swap: array is [3,4,2,5,1]. Inversions: (3,2), (3,1), (4,2), (4,1), (2,1), (5,1) = 6.

🧠 Conceptual

expert

Minimum number of swaps to sort array equals inversion count?

Is the minimum number of swaps required to sort an array always equal to the number of inversions in the array?

A Yes, but only for arrays with distinct elements

B Yes, minimum swaps always equal inversion count

C No, minimum swaps can be more than inversion count

D No, minimum swaps can be less than inversion count

💡 Hint

Think about cycles in the array and how swaps fix them.

Minimum swaps depend on cycle decomposition and can be less than total inversions.