Bird
Raised Fist0
DSA C++programming~5 mins

Count Inversions in Array in DSA C++ - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Count Inversions in Array
O(n log n)
Understanding Time Complexity

We want to understand how long it takes to count inversions in an array as the array grows.

The question is: how does the work increase when the array size gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


int merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid, k = left, inv_count = 0;
    while (i < mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else {
            temp[k++] = arr[j++];
            inv_count += (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 inv_count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
    int inv_count = 0;
    if (left < right) {
        int mid = (left + right) / 2;
        inv_count += mergeSort(arr, temp, left, mid);
        inv_count += mergeSort(arr, temp, mid + 1, right);
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}

This code counts how many pairs of elements are out of order by using a merge sort approach.

Identify Repeating Operations
  • Primary operation: The merge function compares and merges parts of the array repeatedly.
  • How many times: The mergeSort function splits the array recursively, calling merge on smaller parts until the whole array is processed.
How Execution Grows With Input

As the array size grows, the number of operations grows in a pattern where the array is split and merged repeatedly.

Input Size (n)Approx. Operations
10About 50 to 70 operations
100About 700 to 900 operations
1000About 10,000 to 15,000 operations

Pattern observation: The operations grow a bit faster than linear but much slower than quadratic, roughly n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to count inversions grows a little more than linearly as the array size increases, thanks to the efficient merge sort method.

Common Mistake

[X] Wrong: "Counting inversions must check every pair, so it always takes n squared time."

[OK] Correct: The merge sort method cleverly counts inversions while sorting, avoiding checking every pair directly, which makes it much faster.

Interview Connect

Understanding this time complexity shows you can analyze and improve algorithms beyond simple methods, a skill valued in problem solving and coding interviews.

Self-Check

"What if we used a simple nested loop to count inversions instead of merge sort? How would the time complexity change?"

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard