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

Challenge - 5 Problems

❓ Predict Output

intermediate

Count inversions in a small array

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

DSA Rust

fn count_inversions(arr: &mut [i32]) -> i32 {
    let n = arr.len();
    if n <= 1 {
        return 0;
    }
    let mid = n / 2;
    let mut inv_count = 0;
    inv_count += count_inversions(&mut arr[..mid]);
    inv_count += count_inversions(&mut arr[mid..]);

    let mut merged = Vec::with_capacity(n);
    let (mut i, mut j) = (0, mid);
    while i < mid && j < n {
        if arr[i] <= arr[j] {
            merged.push(arr[i]);
            i += 1;
        } else {
            merged.push(arr[j]);
            inv_count += (mid - i) as i32;
            j += 1;
        }
    }
    while i < mid {
        merged.push(arr[i]);
        i += 1;
    }
    while j < n {
        merged.push(arr[j]);
        j += 1;
    }
    arr.copy_from_slice(&merged);
    inv_count
}

fn main() {
    let mut arr = [2, 4, 1, 3, 5];
    let result = count_inversions(&mut arr);
    println!("{}", result);
}

A 5

B 4

C 2

D 3

💡 Hint

Count pairs (i, j) where i < j and arr[i] > arr[j].

The code uses a merge sort approach to count inversions. For the array [2, 4, 1, 3, 5], the inversions are (2,1), (4,1), and (4,3), totaling 3.

❓ Predict Output

intermediate

Count inversions in a reversed array

What is the output of this Rust code counting inversions in a reversed array?

DSA Rust

fn count_inversions(arr: &mut [i32]) -> i32 {
    let n = arr.len();
    if n <= 1 {
        return 0;
    }
    let mid = n / 2;
    let mut inv_count = 0;
    inv_count += count_inversions(&mut arr[..mid]);
    inv_count += count_inversions(&mut arr[mid..]);

    let mut merged = Vec::with_capacity(n);
    let (mut i, mut j) = (0, mid);
    while i < mid && j < n {
        if arr[i] <= arr[j] {
            merged.push(arr[i]);
            i += 1;
        } else {
            merged.push(arr[j]);
            inv_count += (mid - i) as i32;
            j += 1;
        }
    }
    while i < mid {
        merged.push(arr[i]);
        i += 1;
    }
    while j < n {
        merged.push(arr[j]);
        j += 1;
    }
    arr.copy_from_slice(&merged);
    inv_count
}

fn main() {
    let mut arr = [5, 4, 3, 2, 1];
    let result = count_inversions(&mut arr);
    println!("{}", result);
}

A 5

B 10

C 9

D 15

💡 Hint

A reversed array has the maximum number of inversions.

For an array of size 5 reversed, the number of inversions is n*(n-1)/2 = 10.

🔧 Debug

advanced

Identify the error in inversion count code

What error does the following Rust code produce when counting inversions?

DSA Rust

fn count_inversions(arr: &mut [i32]) -> i32 {
    let n = arr.len();
    if n <= 1 {
        return 0;
    }
    let mid = n / 2;
    let mut inv_count = 0;
    inv_count += count_inversions(&mut arr[..mid]);
    inv_count += count_inversions(&mut arr[mid..]);

    let mut merged = Vec::with_capacity(n);
    let (mut i, mut j) = (0, mid);
    while i < mid && j < n {
        if arr[i] < arr[j] {
            merged.push(arr[i]);
            i += 1;
        } else {
            merged.push(arr[j]);
            inv_count += (mid - i) as i32;
            j += 1;
        }
    }
    while i < mid {
        merged.push(arr[i]);
        i += 1;
    }
    while j < n {
        merged.push(arr[j]);
        j += 1;
    }
    arr.copy_from_slice(&merged);
    inv_count
}

fn main() {
    let mut arr = [2, 4, 1, 3, 5];
    let result = count_inversions(&mut arr);
    println!("{}", result);
}

A The code outputs 2 instead of 3

B The code panics with index out of bounds

C The code does not compile due to syntax error

D The code outputs 4 instead of 3

💡 Hint

Check the comparison operator in the merge step.

The code uses '<' instead of '<=' in the merge comparison, causing it to miss counting some inversions.

🧠 Conceptual

advanced

Understanding inversion count complexity

What is the time complexity of counting inversions using the merge sort approach on an array of size n?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

💡 Hint

Think about how merge sort divides and merges the array.

The merge sort approach divides the array and merges in O(n log n) time, counting inversions during merge.

🚀 Application

expert

Count inversions in a large array efficiently

Given an array of 1,000,000 integers, which approach is best to count inversions efficiently?

A Sort the array and count inversions by comparing sorted positions

B Use a brute force nested loop checking all pairs

C Use merge sort based inversion counting algorithm

D Use a hash map to count inversions directly

💡 Hint

Consider time complexity and scalability.

Brute force is O(n^2) and too slow. Merge sort based counting is O(n log n) and efficient for large arrays.

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