Count Inversions in Array in DSA Python - Build from Scratch

Count Inversions in Array

📖 Scenario: You have a list of numbers representing the order of books on a shelf. You want to find out how many pairs of books are out of order compared to the sorted order. This helps you understand how messy the shelf is.

🎯 Goal: Build a program that counts the number of inversions in an array. An inversion is a pair of elements where the first element is bigger but appears before the smaller one.

📋 What You'll Learn

Create a list called books with the exact values [8, 4, 2, 1]

Create a variable called inversion_count and set it to 0

Use a nested for loop with variables i and j to compare elements in books

Increase inversion_count by 1 each time you find an inversion where books[i] > books[j] and i < j

Print the value of inversion_count

💡 Why This Matters

🌍 Real World

Counting inversions is useful in sorting algorithms and understanding how far a list is from being sorted, like checking how messy a shelf is.

💼 Career

This concept is important in software development for optimizing sorting and analyzing data order, useful in fields like data science and algorithm design.

1

Create the list of books

Create a list called books with these exact values: [8, 4, 2, 1]

DSA Python

# Create the list called books with values [8, 4, 2, 1]
# Your code here

Hint

Use square brackets [] to create a list and separate numbers with commas.

2

Set up the inversion counter

Create a variable called inversion_count and set it to 0

DSA Python

books = [8, 4, 2, 1]
# Create a variable inversion_count and set it to 0
# Your code here

Hint

This variable will keep track of how many inversions you find.

3

Count the inversions using nested loops

Use a nested for loop with variables i and j to compare elements in books. Increase inversion_count by 1 each time you find an inversion where books[i] > books[j] and i < j

DSA Python

books = [8, 4, 2, 1]
inversion_count = 0
# Use nested for loops to count inversions
# Your code here

Hint

Use range(len(books)) to loop over indices. Compare pairs where the first index is less than the second.

4

Print the total inversion count

Print the value of inversion_count

DSA Python

books = [8, 4, 2, 1]
inversion_count = 0
for i in range(len(books)):
    for j in range(i + 1, len(books)):
        if books[i] > books[j]:
            inversion_count += 1
# Print the inversion_count
# Your code here

Hint

Use print(inversion_count) to show the result.

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