Count Inversions – GeeksforGeeks Solution Explained

If you’re preparing for coding interviews, the “Count Inversions” problem is a classic and important question. In this blog, we’ll explain the problem, walk you through the brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Given an array of integers arr[]. Find the Inversion Count in the array.
Two elements arr[i] and arr[j] form an inversion if arr[i] > arr[j] and i < j.

Here’s the [Problem Link] to begin with.

Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0.
If an array is sorted in the reverse order then the inversion count is the maximum. 

Examples:

Input: arr[] = [2, 4, 1, 3, 5]
Output: 3
Explanation: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

Input: arr[] = [2, 3, 4, 5, 6]
Output: 0
Explanation: As the sequence is already sorted so there is no inversion count.

Input: arr[] = [10, 10, 10]
Output: 0
Explanation: As all the elements of array are same, so there is no inversion count.

Constraints:
1 ≤ arr.size() ≤ 10⁵
1 ≤ arr[i] ≤ 10⁴

Brute Force Solution (Nested Loops)

Intuition and Approach

Let’s solve the problem in the simplest way:

1. Check Every Pair:
   For each element, compare it with every element that comes after it.
2. Count Inversions:
   If the current element is greater than the next one, it’s an inversion.
3. Why does this work?
   We check all possible pairs, so we count every inversion.

This approach is easy to understand but not efficient for large arrays.

Code Implementation

class Solution:
    def inversionCount(self, arr):
        n = len(arr)
        count = 0
        for i in range(0, n):
            for j in range(i + 1, n):
                if arr[i] > arr[j]:      # found an inversion
                    count += 1
        return count

Code Explanation

• We use two nested loops.
• For each pair (i, j) where i < j, we check if arr[i] > arr[j].
• If true, we increment the inversion count.

Dry Run

Input:
arr = [1]

• (2,4): no inversion
• (2,1): inversion (count = 1)
• (2,3): no inversion
• (2,5): no inversion
• (4,1): inversion (count = 2)
• (4,3): inversion (count = 3)
• (4,5): no inversion
• (1,3): no inversion
• (1,5): no inversion
• (3,5): no inversion

Final count:
3

Time and Space Complexity

• Time Complexity: O(n^2)
  Two nested loops for all pairs.
• Space Complexity: O(1)
  Only a counter variable is used.

Conclusion

The brute force approach is simple and good for understanding, but it’s too slow for large arrays.

Optimal Solution (Merge Sort Approach)

Intuition and Approach

We can count inversions much faster using a modified merge sort:

1. Divide and Conquer:
   Use merge sort to divide the array into smaller parts.
2. Count Inversions During Merge:
   While merging two sorted halves, if an element from the right half is less than an element from the left, it means all remaining elements in the left half will form inversions with this right element.
3. Why does this work?
   Merge sort naturally compares and sorts elements, so it’s efficient to count inversions during the merge step.

This approach is efficient and works well for large arrays.

Code Implementation

from typing import List, Tuple

class Solution:
    def mergeList(self, arr1: List[int], arr2: List[int]) -> Tuple[List[int], int]:
        n = len(arr1)
        m = len(arr2)
        i, j = 0, 0
        count = 0
        result = []

        while i < n and j < m:
            if arr1[i] <= arr2[j]:
                result.append(arr1[i])           # no inversion, add element
                i += 1
            else:
                count += n - i                   # count inversions
                result.append(arr2[j])           # add element from right half
                j += 1

        while i < n:
            result.append(arr1[i])               # add remaining left half elements
            i += 1
        while j < m:
            result.append(arr2[j])               # add remaining right half elements
            j += 1

        return result, count

    def mergeSort(self, lst: List[int]) -> Tuple[List[int], int]:
        if len(lst) <= 1:
            return lst, 0                        # base case, no inversions

        mid = len(lst) // 2
        first_half = lst[:mid]
        second_half = lst[mid:]

        fh, cnt1 = self.mergeSort(first_half)    # sort and count left side
        sh, cnt2 = self.mergeSort(second_half)   # sort and count right side

        merged, count = self.mergeList(fh, sh)   # merge and count split inversions
        return merged, cnt1 + cnt2 + count

    def inversionCount(self, arr: List[int]) -> int:
        _, count = self.mergeSort(arr)
        return count

Code Explanation

• We use a modified merge sort.
• During the merge step, if an element in the left half is greater than one in the right, all remaining elements in the left half will form inversions with this right element.
• We count these inversions and add them to the total.

Dry Run

Input:
arr = [1]

• Split into  and
•  splits into and 
•  splits into and 
• Merge and : inversion (4,1) → count = 1
• Merge and : inversion (2,1) → count = 2
• Merge and : no inversion
• Merge  and : inversion (4,3) → count = 3

Final count:
3

Time and Space Complexity

• Time Complexity: O(n log n)
  Merge sort divides and merges arrays efficiently.
• Space Complexity: O(n)
  Extra space is used for temporary arrays during merge.

Conclusion

The optimal solution is efficient and works well for large arrays. It’s the best approach for interviews and practical use.

Final Thoughts

The “Count Inversions” problem is a great example of how to optimize from brute force to an efficient divide-and-conquer solution. Start with brute force to understand the basics, then use the merge sort approach for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.