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

Challenge - 5 Problems

❓ Predict Output

intermediate

Count Inversions Output for Small Array

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

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    int count = 0;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> leftArr(n1), rightArr(n2);
    for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
            count += (n1 - i);
        }
    }
    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
    return count;
}

int mergeSortAndCount(vector<int>& arr, int left, int right) {
    int count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        count += mergeSortAndCount(arr, left, mid);
        count += mergeSortAndCount(arr, mid + 1, right);
        count += mergeAndCount(arr, left, mid, right);
    }
    return count;
}

int main() {
    vector<int> arr = {2, 4, 1, 3, 5};
    int result = mergeSortAndCount(arr, 0, arr.size() - 1);
    cout << result << endl;
    return 0;
}

A 3

B 4

C 2

D 5

💡 Hint

Count pairs where a larger number appears before a smaller number.

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

❓ Predict Output

intermediate

Count Inversions Output for Sorted Array

What is the output of the following C++ code that counts inversions in a sorted array?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    int count = 0;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> leftArr(n1), rightArr(n2);
    for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
            count += (n1 - i);
        }
    }
    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
    return count;
}

int mergeSortAndCount(vector<int>& arr, int left, int right) {
    int count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        count += mergeSortAndCount(arr, left, mid);
        count += mergeSortAndCount(arr, mid + 1, right);
        count += mergeAndCount(arr, left, mid, right);
    }
    return count;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int result = mergeSortAndCount(arr, 0, arr.size() - 1);
    cout << result << endl;
    return 0;
}

A 0

B 4

C 1

D 5

💡 Hint

A sorted array has no inversions.

Since the array is sorted ascending, no pairs are inverted.

🔧 Debug

advanced

Identify the Bug in Inversion Count Merge Function

The following merge function is intended to count inversions during merge sort. What is the bug causing incorrect inversion count?

DSA C++

int mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    int count = 0;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> leftArr(n1), rightArr(n2);
    for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
            count += (n1 - i);
        }
    }
    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
    return count;
}

A The function should return count + 1 to include the last inversion.

B The count increment should be (n2 - j) instead of (n1 - i).

C The loops copying to leftArr and rightArr use <= instead of < causing out-of-bounds access.

D The comparison should be < instead of <= to count equal elements as inversions.

💡 Hint

Check array indexing in the copying loops.

Using <= causes the loops to access one element beyond array bounds, leading to undefined behavior and wrong counts.

🧠 Conceptual

advanced

Why Use Merge Sort to Count Inversions?

Why is merge sort a good choice to count inversions in an array efficiently?

A Because merge sort sorts the array in place without extra memory.

B Because merge sort counts inversions by comparing every pair in O(n^2) time.

C Because merge sort uses a stack to track inversions explicitly.

D Because merge sort divides the array and counts inversions during merging in O(n log n) time.

💡 Hint

Think about how merge sort combines sorted halves.

Merge sort counts inversions while merging two sorted halves, achieving O(n log n) time, better than naive O(n^2).

🚀 Application

expert

Count Inversions in Large Array with Duplicates

Given the array [3, 3, 2, 2, 1, 1], what is the total number of inversions counted by the standard merge sort inversion count algorithm?

A 18

B 12

C 15

D 9

💡 Hint

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

Inversions are (3,2), (3,1), (2,1) pairs counted with duplicates. Total is 12.

Practice

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

easy

A. The sum of all elements in the array

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. A pair of elements where the first is greater than the second and appears before it

Solution

1. Step 1: Understand the definition of inversion

   An inversion is a pair (i, j) such that i < j and 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 matches the 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 D

4. Quick Check:

   Inversion = pair with first > second [OK]

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

Common Mistakes:

• Confusing inversion with sorted pairs
• Thinking inversion counts total elements
• Mixing up greater and smaller conditions

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

easy

A. int countInversions(vector<int>& arr);

B. void countInversions(vector<int> arr);

C. int countInversions(int arr[]);

D. int countInversions(vector<int> arr);

Solution

1. Step 1: Check function return type and parameter passing

   The function should return an integer count and take array by reference for efficiency.

2. Step 2: Analyze each option

   int countInversions(vector<int>& arr); returns int and takes vector by reference, correct. void countInversions(vector<int> arr); returns void, wrong. int countInversions(int arr[]); uses raw array without size info, less preferred. int countInversions(vector<int> arr); passes vector by value, inefficient.

3. Final Answer:

   int countInversions(vector<int>& arr); -> Option A

4. Quick Check:

   Return int, pass vector by reference [OK]

Hint: Count returns int; pass vector by reference to avoid copying [OK]

Common Mistakes:

• Using void return type
• Passing vector by value causing copies
• Using raw arrays without size info

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

std::vector<int> arr = {2, 4, 1, 3, 5};
int count = 0;
for (int i = 0; i < arr.size(); i++) {
  for (int j = i + 1; j < arr.size(); j++) {
    if (arr[i] > arr[j]) count++;
  }
}
std::cout << count << std::endl;

medium

A. 2

B. 4

C. 3

D. 5

Solution

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

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

2. Step 2: Count these pairs

   There are exactly 3 such pairs.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Inversions = 3 [OK]

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

Common Mistakes:

• Counting pairs where first is smaller
• Missing some inversion pairs
• Confusing index order

4. Find the error in this C++ function to count inversions using a brute force approach:

int countInversions(std::vector<int> arr) {
  int count = 0;
  for (int i = 0; i < arr.size(); i++) {
    for (int j = 0; j < arr.size(); j++) {
      if (arr[i] > arr[j]) count++;
    }
  }
  return count;
}

medium

A. Function should return void, not int

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

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

D. Count variable should be initialized outside the function

Solution

1. Step 1: Analyze loop ranges for counting inversions

   Inversion pairs require i < j, so inner loop must start from j = i + 1.

2. Step 2: Identify the error in the given code

   Inner loop starts from 0, counting pairs twice and including invalid pairs where j < i.

3. Final Answer:

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

4. Quick Check:

   Inner loop from i+1 to end [OK]

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

Common Mistakes:

• Starting inner loop from 0 causing double counting
• Wrong comparison direction
• Incorrect return type

5. Given the array {8, 4, 2, 1}, what is the number of inversions using an efficient merge sort based approach?

hard

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Understand inversions in the array

   All pairs where first > second and first index < second index are: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1).

2. Step 2: Count inversions carefully

   There are 6 pairs total, but merge sort counts inversions during merging. The efficient approach counts 6 inversions.

3. Step 3: Verify merge sort inversion count

   Merge sort counts 6 inversions for this array.

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Inversions = 6 [OK]

Hint: Count pairs where left element is bigger during merge [OK]

Common Mistakes:

• Under-counting inversions by missing pairs
• Confusing brute force and merge sort counts
• Miscounting pairs with equal elements