Count Inversions in Array in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an inversion in an array?

An inversion is a pair of elements where the first element is greater than the second element, but the first element appears before the second in the array.

beginner

Why do we count inversions in an array?

Counting inversions helps measure how far the array is from being sorted. More inversions mean the array is less sorted.

beginner

What is the time complexity of the naive method to count inversions?

The naive method compares every pair and has a time complexity of O(n²), where n is the number of elements.

intermediate

How does the merge sort method help count inversions efficiently?

During merge sort, when merging two sorted halves, we count how many elements from the right half are placed before elements from the left half, which indicates inversions. This reduces time complexity to O(n log n).

intermediate

What is the key step to count inversions during the merge process?

When an element from the right half is smaller than an element from the left half, all remaining elements in the left half form inversions with that right element.

What does an inversion in an array represent?

A A pair where the first element is greater and appears before the second

B A pair where the first element is smaller and appears before the second

C Two equal elements next to each other

D Any two elements in the array

An inversion is when a bigger number comes before a smaller number in the array.

What is the time complexity of counting inversions using merge sort?

A O(n²)

B O(n)

C O(log n)

D O(n log n)

Merge sort counts inversions efficiently in O(n log n) time.

During merge sort, when do we count inversions?

A When merging two sorted halves

B When splitting the array

C Before sorting starts

D After the array is fully sorted

Inversions are counted during the merge step when combining sorted halves.

If the array is already sorted, how many inversions does it have?

A Maximum inversions

B Zero inversions

C Half the number of elements

D Cannot be determined

A sorted array has zero inversions because no element is out of order.

What is the naive approach to count inversions?

A Use binary search

B Use merge sort

C Compare every pair of elements

D Use a hash map

The naive method checks every pair to find inversions, which is slow.

Explain how merge sort can be used to count inversions in an array.

Think about how merging two sorted lists reveals inversions.

Describe what an inversion is and why counting inversions is useful.

Imagine how many swaps needed to sort the array.

Practice

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

easy

A. The total number of elements in the array

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

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

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 matches this definition exactly, others describe different concepts.

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 inversion with total pairs

2. Which of the following C code snippets correctly declares a function to count inversions in an array?

easy

A. int countInversions(int arr[], int n);

B. void countInversions(int arr[], int n);

C. int countInversions(int arr, int n[]);

D. int countInversions(int *arr, int n[]);

Solution

1. Step 1: Check function signature correctness

   The function should return an integer count and take an integer array and its size as parameters.

2. Step 2: Analyze each option

   int countInversions(int arr[], int n); correctly uses int return type and parameters as int arr[] and int n. Others have wrong parameter types or return type.

3. Final Answer:

   int countInversions(int arr[], int n); -> Option A

4. Quick Check:

   Correct function signature returns int and takes int array and size [OK]

Hint: Function returns int and takes int array plus size [OK]

Common Mistakes:

• Using void return type instead of int
• Swapping array and size parameter types
• Using pointer syntax incorrectly

3. What is the output of the following C code snippet?

int arr[] = {2, 4, 1, 3, 5};
int n = 5;
int count = 0;
for(int i = 0; i < n-1; i++) {
  for(int j = i+1; j < n; j++) {
    if(arr[i] > arr[j]) count++;
  }
}
printf("%d", count);

medium

A. 5

B. 4

C. 3

D. 2

Solution

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

   Pairs where first element is greater than second: (2,1), (4,1), (4,3). Total = 3.

2. Step 2: Confirm count variable increments correctly

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

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Inversions = 3 [OK]

Hint: Count pairs where left element > right element [OK]

Common Mistakes:

• Counting pairs where left < right
• Missing some inversion pairs
• Off-by-one errors in loops

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

int countInversions(int arr[], int n) {
  int count = 0;
  for(int i = 0; i < n; i++) {
    for(int j = i; j < n; j++) {
      if(arr[i] >= arr[j]) count++;
    }
  }
  return count;
}

medium

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

B. The count variable should be initialized outside the function

C. The comparison should be arr[i] < arr[j]

D. The function should return void instead of int

Solution

1. Step 1: Analyze loop ranges for counting pairs

   Inner loop starts at j = i, so it compares arr[i] with itself, causing incorrect counting.

2. Step 2: Correct inner loop start index

   Inner loop should start at j = i + 1 to avoid self-comparison.

3. Final Answer:

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

4. Quick Check:

   Start inner loop at i+1 to avoid self-comparison [OK]

Hint: Inner loop must start after outer loop index [OK]

Common Mistakes:

• Starting inner loop at same index as outer
• Wrong comparison operator
• Returning wrong type

5. Given the array {8, 4, 2, 1}, what is the total number of inversions? Also, explain why this number represents the worst case for inversion counting.

hard

A. 4

B. 0

C. 3

D. 6

Solution

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

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

2. Step 2: Understand why this is worst case

   The array is sorted in descending order, so every pair is inverted, maximum inversions possible for size 4.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Descending order 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 inversions
• Forgetting pairs with elements far apart
• Confusing inversion count with array length