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.

Practice

1. What does the term inversion in an array mean?

easy

A. A pair of elements where the first is smaller than the second and appears before it

B. A pair of elements where the first is greater than the second and appears before it

C. The total number of elements in the array

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

   An inversion is when a larger number appears before a smaller number in the array.

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it correctly describes this pair condition, others do not.

3. Final Answer:

   A pair of elements where the first is greater than the second and appears before it -> Option B

4. Quick Check:

   Inversion = larger before smaller [OK]

Hint: Inversion means bigger number comes before smaller one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal elements
• Mixing up element positions

2. Which of the following Python code snippets correctly counts inversions using a simple nested loop?

easy

A. count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1

B. count = 0
for i in range(len(arr)):
for j in range(i):
if arr[i] > arr[j]:
count += 1

C. count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] < arr[j]:
count += 1

D. count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j]:
count += 1

Solution

1. Step 1: Check the loop ranges and condition

   count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] > arr[j]: count += 1 loops i from 0 to end and j from i+1 to end, comparing arr[i] > arr[j]. This matches inversion definition.

2. Step 2: Verify other options

   count = 0 for i in range(len(arr)): for j in range(i): if arr[i] > arr[j]: count += 1 checks arr[i] > arr[j] but loops j before i, counting later > earlier which is incorrect. count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] < arr[j]: count += 1 counts when arr[i] < arr[j], which is not inversion. count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] == arr[j]: count += 1 counts equal elements, not inversions.

3. Final Answer:

   count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] > arr[j]: count += 1 -> Option A

4. Quick Check:

   Nested loops with arr[i] > arr[j] count inversions [OK]

Hint: Use nested loops with j > i and check arr[i] > arr[j] [OK]

Common Mistakes:

• Checking arr[i] < arr[j] instead of >
• Looping j before i
• Counting equal elements as inversions

3. What is the output of the following code?

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

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

medium

A. 5

B. 4

C. 2

D. 3

Solution

1. Step 1: Identify all inversion pairs in the array

   Array: [2, 4, 1, 3, 5]. Inversions are (2,1), (4,1), (4,3). Total 3 inversions.

2. Step 2: Confirm code counts these correctly

   Code loops through pairs and increments count for each inversion found, so returns 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count inversions in [2,4,1,3,5] = 3 [OK]

Hint: Count pairs where earlier number is bigger [OK]

Common Mistakes:

• Missing some inversion pairs
• Counting pairs with equal elements
• Confusing order of pairs

4. Find the error in this code snippet for counting inversions:

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

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

medium

A. The inner loop should start from i+1, not 0 to i

B. The count variable is not initialized

C. The comparison should be arr[i] < arr[j] instead of arr[i] > arr[j]

D. The function does not return any value

Solution

1. Step 1: Analyze loop ranges and comparison

   Inner loop runs j from 0 to i-1, so j < i. The code checks if arr[i] > arr[j], counting pairs where later element is bigger.

2. Step 2: Identify correct inversion condition

   Inversion means earlier element is bigger than later one, so condition should be arr[j] > arr[i]. Current condition is reversed, causing wrong count.

3. Final Answer:

   The comparison should be arr[i] < arr[j] instead of arr[i] > arr[j] -> Option C

4. Quick Check:

   Inversion needs earlier > later, fix comparison [OK]

Hint: Check if earlier element is greater, not later [OK]

Common Mistakes:

• Reversing comparison operator
• Wrong loop ranges causing missed pairs
• Not returning count

5. Given the array [8, 4, 2, 1], what is the number of inversions? Also, explain why this count represents the worst case for inversion counting algorithms.

hard

A. 6; because the array is sorted in descending order, all pairs are inversions

B. 4; because only adjacent pairs are inversions

C. 0; because the array is sorted ascending

D. 3; because only some pairs are inversions

Solution

1. Step 1: Count all inversion pairs in the array

   Array: [8, 4, 2, 1]. Inversions: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) = 6 total.

2. Step 2: Explain why this is worst case

   Array sorted descending means every pair is inverted. Algorithms checking pairs must count all, causing maximum work.

3. Final Answer:

   6; because the array is sorted in descending order, all pairs are inversions -> Option A

4. Quick Check:

   Descending array has max inversions = n(n-1)/2 [OK]

Hint: Descending order array has max inversions n(n-1)/2 [OK]

Common Mistakes:

• Counting only adjacent pairs
• Confusing ascending with descending
• Not recognizing worst case scenario