Why Count Inversions in Array in DSA C#?

The Big Idea

What if you could instantly know how mixed up your list is without checking every pair?

The Scenario

Imagine you have a list of numbers representing the order of books on a shelf, but they are not sorted. You want to know how many pairs of books are out of order compared to a sorted shelf.

The Problem

Manually checking every pair to see if they are out of order takes a very long time when the list is large. It is easy to miss pairs or count some twice, making the process slow and error-prone.

The Solution

Counting inversions with an efficient method quickly finds how many pairs are out of order without checking each pair one by one. This saves time and reduces mistakes.

Before vs After

✗ Before

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;
}

✓ After

int MergeSortAndCount(int[] arr, int left, int right) {
  if (left >= right) return 0;
  int mid = (left + right) / 2;
  int count = MergeSortAndCount(arr, left, mid) + MergeSortAndCount(arr, mid + 1, right);
  count += MergeAndCount(arr, left, mid, right);
  return count;
}

What It Enables

This lets you quickly measure how far a list is from being sorted, which helps in sorting optimization and understanding data disorder.

Real Life Example

In sports rankings, counting inversions helps find how many pairs of teams are ranked differently compared to last season, showing changes in performance.

Key Takeaways

Manual pair checking is slow and error-prone.

Efficient counting uses divide and conquer to speed up the process.

Useful for measuring disorder and optimizing sorting.

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