Count Inversions in Array in DSA Python

Mental Model

Count how many pairs of numbers are out of order in an array. Each pair where a bigger number comes before a smaller one is an inversion.

Analogy: Imagine a line of people waiting by height. Every time a taller person stands before a shorter one, it's like an inversion. Counting all these pairs tells us how mixed up the line is.

Array: [2, 4, 1, 3, 5]
Inversions: (2,1), (4,1), (4,3)
Visual:
2 -> 4 -> 1 -> 3 -> 5
 ↑    ↑    ↑    ↑    ↑

Dry Run Walkthrough

Input: array: [2, 4, 1, 3, 5]

Goal: Count all pairs where a bigger number appears before a smaller number

Step 1: Split array into two halves: left=[2,4,1], right=[3,5]

left: 2 -> 4 -> 1
right: 3 -> 5

Why: Divide to conquer: easier to count inversions by merging sorted halves

Step 2: Split left half again: left_left=[2,4], left_right=[1]

left_left: 2 -> 4
left_right: 1

Why: Keep dividing until subarrays have one or zero elements

Step 3: Split left_left into [2] and [4], both single elements

2
4

Why: Base case reached for merge sort

Step 4: Merge [2] and [4] back sorted: [2,4], inversions=0

2 -> 4

Why: No inversion because 2 < 4

Step 5: Merge [2,4] and [1], count inversions where left element > right element

Merge steps:
Compare 2 and 1: 2 > 1, inversion count += 2 (elements left in left array)
Result: 1 -> 2 -> 4

Why: 1 is smaller than 2 and 4, so two inversions here

Step 6: Merge sorted left half [1,2,4] and right half [3,5], count inversions

Compare 1 and 3: no inversion
Compare 2 and 3: no inversion
Compare 4 and 3: 4 > 3, inversion count += 1
Result: 1 -> 2 -> 3 -> 4 -> 5

Why: Only one inversion found here between 4 and 3

Result:

Final sorted array: 1 -> 2 -> 3 -> 4 -> 5
Total inversions counted: 3

Annotated Code

DSA Python

from typing import List, Tuple

class InversionCounter:
    def merge_sort_count(self, arr: List[int]) -> Tuple[List[int], int]:
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, left_inv = self.merge_sort_count(arr[:mid])
        right, right_inv = self.merge_sort_count(arr[mid:])
        merged, split_inv = self.merge_count(left, right)
        return merged, left_inv + right_inv + split_inv

    def merge_count(self, left: List[int], right: List[int]) -> Tuple[List[int], int]:
        i = j = 0
        merged = []
        inversions = 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])
                inversions += len(left) - i  # Count inversions here
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, inversions

if __name__ == '__main__':
    arr = [2, 4, 1, 3, 5]
    counter = InversionCounter()
    sorted_arr, total_inversions = counter.merge_sort_count(arr)
    print('Sorted array:', ' -> '.join(map(str, sorted_arr)) + ' -> null')
    print('Total inversions:', total_inversions)

if len(arr) <= 1:

base case: single element or empty array is already sorted, no inversions

left, left_inv = self.merge_sort_count(arr[:mid])

recursively sort left half and count its inversions

right, right_inv = self.merge_sort_count(arr[mid:])

recursively sort right half and count its inversions

merged, split_inv = self.merge_count(left, right)

merge two sorted halves and count split inversions

if left[i] <= right[j]:

if left element smaller or equal, add it to merged, no new inversion

else:

right element smaller, add it and count inversions equal to remaining left elements

inversions += len(left) - i

count how many left elements are bigger than current right element

Output

Sorted array: 1 -> 2 -> 3 -> 4 -> 5 -> null

Total inversions: 3

Complexity Analysis

Time: O(n log n) because the array is divided and merged recursively, counting inversions during merge

Space: O(n) due to temporary arrays created during merge steps

vs Alternative: Naive approach is O(n^2) by checking all pairs; merge sort method is much faster for large arrays

Edge Cases

empty array

returns 0 inversions immediately

DSA Python

if len(arr) <= 1:

array with one element

returns 0 inversions immediately

DSA Python

if len(arr) <= 1:

array with all elements equal

returns 0 inversions because no element is greater than another

DSA Python

if left[i] <= right[j]:

When to Use This Pattern

When asked to count how many pairs are out of order in an array, use the merge sort inversion counting pattern because it efficiently counts inversions while sorting.

Common Mistakes

Mistake: Counting inversions only when elements are strictly greater, missing equal elements
Fix: Use <= in comparison to avoid counting equal elements as inversions

Mistake: Not adding the number of remaining left elements when a right element is smaller
Fix: Add len(left) - i to inversion count when right[j] < left[i]

Summary

Counts how many pairs in an array are out of order using a modified merge sort.

Use it when you need to find how mixed up an array is compared to sorted order.

The key insight is counting inversions during the merge step by knowing how many left elements remain when a right element is smaller.

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