Count Inversions in Array in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Count inversions in a small array

What is the output of the following C# code that counts inversions in the array?

DSA C#

using System;

class Program {
    static int CountInversions(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.Length; i++) {
            for (int j = i + 1; j < arr.Length; j++) {
                if (arr[i] > arr[j]) count++;
            }
        }
        return count;
    }

    static void Main() {
        int[] array = {2, 4, 1, 3, 5};
        Console.WriteLine(CountInversions(array));
    }
}

A 4

B 5

C 3

D 2

💡 Hint

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

The pairs are (2,1), (4,1), and (4,3). Total 3 inversions.

🧠 Conceptual

intermediate

Understanding inversion count meaning

What does the inversion count in an array represent?

A Number of elements that are out of place compared to a sorted array

B Number of pairs where the first element is greater than the second and appears before it

C Number of pairs where the first element is smaller than the second

D Number of elements equal to the maximum value in the array

💡 Hint

Think about pairs that are in the wrong order.

Inversion count is the number of pairs (i, j) such that i < j and arr[i] > arr[j].

❓ Predict Output

advanced

Output of merge sort based inversion count

What is the output of this C# code that uses merge sort to count inversions?

DSA C#

using System;

class Program {
    static int Merge(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left, j = mid, k = left, invCount = 0;
        while (i < mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                invCount += (mid - i);
            }
        }
        while (i < mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        for (int idx = left; idx <= right; idx++) arr[idx] = temp[idx];
        return invCount;
    }

    static int MergeSort(int[] arr, int[] temp, int left, int right) {
        int invCount = 0;
        if (left < right) {
            int mid = (left + right) / 2;
            invCount += MergeSort(arr, temp, left, mid);
            invCount += MergeSort(arr, temp, mid + 1, right);
            invCount += Merge(arr, temp, left, mid + 1, right);
        }
        return invCount;
    }

    static void Main() {
        int[] array = {8, 4, 2, 1};
        int[] temp = new int[array.Length];
        Console.WriteLine(MergeSort(array, temp, 0, array.Length - 1));
    }
}

A 6

B 5

C 4

D 7

💡 Hint

Count pairs where left element is bigger than right element in the array.

The inversions are (8,4), (8,2), (8,1), (4,2), (4,1), and (2,1) totaling 6.

🔧 Debug

advanced

Identify the bug in inversion count code

What error will this C# code produce when counting inversions?

DSA C#

using System;

class Program {
    static int CountInversions(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.Length; i++) {
            for (int j = i + 1; j < arr.Length; j++) {
                if (arr[i] > arr[j]) count++;
            }
        }
        return count;
    }

    static void Main() {
        int[] array = {1, 3, 2};
        Console.WriteLine(CountInversions(array));
    }
}

A IndexOutOfRangeException

B No error, output is 1

C NullReferenceException

D Compile time error

💡 Hint

Check the loop boundary conditions carefully.

The outer loop uses i <= arr.Length which causes i to go out of bounds when accessing arr[i].

🚀 Application

expert

Minimum swaps to sort array using inversion count concept

Given an array, what is the minimum number of swaps required to sort it? Consider the array [4, 3, 2, 1]. Which option correctly gives the minimum swaps?

A 2

B 6

C 4

D 3

💡 Hint

Minimum swaps to sort is related to cycles in the permutation, not just inversion count.

The array [4,3,2,1] requires 3 swaps to sort: swap 4 and 1, then 3 and 2, then 4 and 2.

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 (i, j) such that i < j but array[i] > array[j].

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 condition, while others describe unrelated 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 array[i] > array[j] [OK]

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

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts pairs where first is smaller
• Counting total elements instead of pairs

2. Which of the following C# code snippets correctly initializes an integer array named arr with values 3, 1, 2?

easy

A. int arr[] = new int[3] {3, 1, 2};

B. int arr = {3, 1, 2};

C. int[] arr = new int[] {3, 1, 2};

D. int arr[] = {3, 1, 2};

Solution

1. Step 1: Review C# array initialization syntax

   In C#, arrays must be declared as int[] arr and can be initialized explicitly with new int[] {values};

2. Step 2: Check each option

   int arr[] = new int[3] {3, 1, 2}; uses invalid declaration syntax (arr[]). int arr = {3, 1, 2}; tries to assign an array to an int. int arr[] = {3, 1, 2}; uses invalid declaration syntax (arr[]). int[] arr = new int[] {3, 1, 2}; uses the correct explicit syntax.

3. Final Answer:

   int[] arr = new int[] {3, 1, 2}; -> Option C

4. Quick Check:

   Correct array init uses new int[] {values} [OK]

Hint: Use new int[] { } to initialize arrays explicitly [OK]

Common Mistakes:

• Omitting new int[] in initialization
• Using C/C++ style array declaration
• Incorrect array size syntax

3. What is the output of the following C# code that counts inversions in the array arr = {2, 4, 1, 3, 5}?

int CountInversions(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.Length - 1; i++) {
        for (int j = i + 1; j < arr.Length; j++) {
            if (arr[i] > arr[j]) count++;
        }
    }
    return count;
}

int[] arr = {2, 4, 1, 3, 5};
Console.WriteLine(CountInversions(arr));

medium

A. 3

B. 4

C. 2

D. 5

Solution

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

   Pairs where first > second and first index < second index: (2,1), (4,1), (4,3) -> total 3 inversions.

2. Step 2: Confirm code counts these pairs

   Nested loops check all pairs; count increments for each inversion found, matching the 3 pairs.

3. Final Answer:

   3 -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Counting pairs where first is smaller
• Missing some inversion pairs
• Off-by-one errors in loops

4. The following code attempts to count inversions but gives wrong output. What is the error?

int CountInversions(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.Length; i++) {
        for (int j = 0; j < arr.Length; j++) {
            if (arr[i] > arr[j]) count++;
        }
    }
    return count;
}

medium

A. The function should return void

B. Comparison should be arr[i] < arr[j]

C. Count variable should be initialized outside the function

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

Solution

1. Step 1: Analyze loop ranges for counting inversions

   Inversion pairs require i < j, but inner loop starts at 0, counting pairs twice and including invalid pairs.

2. Step 2: Fix inner loop start index

   Changing inner loop to start at i+1 ensures only pairs with i < j are counted once.

3. Final Answer:

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

4. Quick Check:

   Count inversions need j > i, so inner loop from i+1 [OK]

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

Common Mistakes:

• Starting inner loop at 0 causing double counting
• Reversing comparison operator
• Misplacing count initialization

5. Given the array arr = {8, 4, 2, 1}, what is the total number of inversions? Use the efficient merge sort based method to count inversions.

hard

A. 7

B. 6

C. 4

D. 5

Solution

1. Step 1: Understand inversions in the array

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

2. Step 2: Count inversions using merge sort method

   Subarrays [8,4] and [2,1] each add 1 inversion (total 2). Final merge of [4,8] and [1,2]: +2 when taking 1, +2 when taking 2 (total 4). Grand total: 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Merge sort inversion count for {8,4,2,1} = 6 [OK]

Hint: Merge sort counts inversions during merge step [OK]

Common Mistakes:

• Counting only direct pairs, missing cross merges
• Using brute force count only
• Misunderstanding merge step inversion counting