Count Inversions in Array in DSA Rust - Build from Scratch

Count Inversions in Array

📖 Scenario: Imagine 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 their correct sorted order. This count is called the number of inversions.

🎯 Goal: You will write a Rust program to count how many pairs of numbers in an array are inverted, meaning the first number is bigger than the second but appears before it in the list.

📋 What You'll Learn

Create a vector called arr with the exact values [2, 4, 1, 3, 5]

Create a variable called inversion_count and set it to 0

Use nested for loops with variables i and j to compare elements in arr

Increment inversion_count when arr[i] > arr[j] and i < j

Print the value of inversion_count

💡 Why This Matters

🌍 Real World

Counting inversions helps measure how far a list is from being sorted, useful in sorting algorithms and analyzing data order.

💼 Career

Understanding inversion counting is important for software engineers working on algorithms, data analysis, and optimization problems.

1

Create the array

Create a vector called arr with the exact values [2, 4, 1, 3, 5].

DSA Rust

# Your code here
// Create a vector called arr with values [2, 4, 1, 3, 5]

Hint

Use let arr = vec![2, 4, 1, 3, 5]; to create the vector.

2

Initialize inversion count

Create a variable called inversion_count and set it to 0 inside the main function after the vector arr.

DSA Rust

fn main() {
    let arr = vec![2, 4, 1, 3, 5];
    // Create a variable inversion_count and set it to 0
    // Your code here
}

Hint

Use let mut inversion_count = 0; to create a mutable counter.

3

Count inversions with nested loops

Use nested for loops with variables i and j to compare elements in arr. Increment inversion_count when arr[i] > arr[j] and i < j.

DSA Rust

fn main() {
    let arr = vec![2, 4, 1, 3, 5];
    let mut inversion_count = 0;
    // Use nested for loops to count inversions
    // Your code here
}

Hint

Use for i in 0..arr.len() and inside it for j in i+1..arr.len(). Compare arr[i] and arr[j]. Increase inversion_count if arr[i] > arr[j].

4

Print the inversion count

Print the value of inversion_count using println! inside the main function.

DSA Rust

fn main() {
    let arr = vec![2, 4, 1, 3, 5];
    let mut inversion_count = 0;
    for i in 0..arr.len() {
        for j in i+1..arr.len() {
            if arr[i] > arr[j] {
                inversion_count += 1;
            }
        }
    }
    // Print the inversion_count
    // Your code here
}

Hint

Use println!("{}", inversion_count); to show the count.

Practice

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

easy

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

B. A pair of elements where the first is smaller 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 a pair of elements where the first element is greater than the second and appears before it 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 matches this definition exactly, while others describe different concepts.

3. Final Answer:

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

4. Quick Check:

   Inversion = pair (i, j) with i < j and arr[i] > arr[j] [OK]

Hint: Inversion means earlier bigger number than a later one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts total elements
• Mixing up greater and smaller element order

2. Which Rust code snippet correctly declares a function to count inversions in an array slice?

easy

A. fn count_inversions(arr: &[i32]) -> i32 { 0 }

B. fn count_inversions(arr: Vec i32 { 0 }

C. fn count_inversions(arr: &[i32]) -> usize { 0 }

D. fn count_inversions(arr: &mut [i32]) -> usize { 0 }

Solution

1. Step 1: Identify correct function signature for counting inversions

   The function should take an immutable slice of integers and return the count as usize (non-negative integer).

2. Step 2: Compare options

   fn count_inversions(arr: &[i32]) -> usize { 0 } uses &[i32] for input and usize for output, which is correct. fn count_inversions(arr: Vec i32 { 0 } takes ownership (Vec) and returns i32 (can be negative). fn count_inversions(arr: &mut [i32]) -> usize { 0 } uses mutable slice unnecessarily. fn count_inversions(arr: &[i32]) -> i32 { 0 } returns i32 which can be negative, not ideal for count.

3. Final Answer:

   fn count_inversions(arr: &[i32]) -> usize { 0 } -> Option C

4. Quick Check:

   Immutable slice input + usize output = correct signature [OK]

Hint: Use &[i32] input and usize output for count functions [OK]

Common Mistakes:

• Using Vec instead of slice for input
• Returning signed integer for count
• Using mutable slice when not needed

3. What is the output of the following Rust code snippet counting inversions?

fn main() {
    let arr = [2, 4, 1, 3, 5];
    let mut count = 0;
    for i in 0..arr.len() {
        for j in i+1..arr.len() {
            if arr[i] > arr[j] {
                count += 1;
            }
        }
    }
    println!("{}", count);
}

medium

A. 4

B. 3

C. 2

D. 5

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 count from nested loops

   Loops check all pairs i < j. Each inversion increments count by 1. Final count is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Count inversions by pairs = 3 [OK]

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

Common Mistakes:

• Counting non-inversion pairs
• Missing some inversion pairs
• Confusing indices order

4. The following Rust code attempts to count inversions but has a bug. What is the bug?

fn count_inversions(arr: &[i32]) -> usize {
    let mut count = 0;
    for i in 0..arr.len() {
        for j in 0..arr.len() {
            if arr[i] > arr[j] {
                count += 1;
            }
        }
    }
    count
}

medium

A. Inner loop should start from i+1, not 0

B. Count variable should be i32, not usize

C. Function should take mutable slice

D. Comparison operator should be < instead of >

Solution

1. Step 1: Analyze loop ranges for counting inversions

   Inversion counts pairs where i < j and arr[i] > arr[j]. Inner loop starting at 0 compares all pairs including i >= j, causing double counting and invalid pairs.

2. Step 2: Correct inner loop start index

   Inner loop should start at i+1 to ensure only pairs with i < j are counted once.

3. Final Answer:

   Inner loop should start from i+1, not 0 -> Option A

4. Quick Check:

   Loop indices must ensure i < j for correct inversion count [OK]

Hint: Inner loop must start after outer index to avoid double count [OK]

Common Mistakes:

• Starting inner loop at 0 causing double counting
• Using wrong comparison operator
• Changing input slice to mutable unnecessarily

5. Given the array [8, 4, 2, 1], what is the number of inversions? Use the merge sort based approach to count inversions efficiently.

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Understand merge sort inversion counting

   Merge sort counts inversions by counting how many elements from right subarray are placed before left subarray elements during merge.

2. Step 2: Count inversions in [8,4,2,1]

   Pairs: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) total 6 inversions.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   All pairs where left > right count to 6 [OK]

Hint: Count pairs where left number bigger than right during merge [OK]

Common Mistakes:

• Counting only adjacent pairs
• Missing some inversion pairs
• Confusing merge sort steps