Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Inversion Count in Array

HARDProblemSolveExternal Links

Description

Given an array of N integers, count the total number of inversions in the array.

An inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j]. In other words, an inversion occurs whenever a larger element appears before a smaller element in the array.

The inversion count tells us how far the array is from being sorted. A fully sorted array (ascending order) has 0 inversions, while an array sorted in descending order has the maximum possible inversions.

Think of it this way: every time you find two elements that are in the "wrong order" relative to each other (the earlier one is bigger than the later one), that is one inversion. Your job is to count how many such "wrong order" pairs exist in the entire array.

Examples

Example 1

Input: arr = [2, 4, 1, 3, 5]

Output: 3

Explanation: The inversions are:

  • (0, 2): arr[0]=2 > arr[2]=1
  • (1, 2): arr[1]=4 > arr[2]=1
  • (1, 3): arr[1]=4 > arr[3]=3

These are the only pairs where the earlier element is larger than the later one. Total inversions = 3.

Example 2

Input: arr = [4, 3, 2, 1]

Output: 6

Explanation: Every pair is an inversion since the array is sorted in descending order:

  • (0,1): 4>3, (0,2): 4>2, (0,3): 4>1
  • (1,2): 3>2, (1,3): 3>1
  • (2,3): 2>1

Total inversions = 6 = 4×3/2 (maximum for an array of size 4).

Example 3

Input: arr = [1, 2, 3, 4, 5]

Output: 0

Explanation: The array is already sorted in ascending order. No element is greater than any element that comes after it. Therefore, there are zero inversions.

Constraints

  • 1 ≤ N ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^9

Editorial

Brute Force

Intuition

The most direct approach is to check every possible pair of elements in the array. For each element at index i, we look at every element at index j where j > i. If the element at i is greater than the element at j, we have found an inversion and increment our counter.

Imagine you are a teacher checking a line of students sorted by height. You pick each student one at a time and compare their height with every student standing behind them. Every time you find a shorter student standing behind a taller one, you count that as one "out of order" pair. By the time you have compared every student with everyone behind them, you have the total number of out-of-order pairs — the inversion count.

Step-by-Step Explanation

Let's trace through with arr = [2, 4, 1, 3, 5]:

Step 1: Fix i=0 (value 2). Compare with all elements after it.

  • j=1: arr[0]=2, arr[1]=4. Is 2 > 4? No. No inversion.
  • j=2: arr[0]=2, arr[2]=1. Is 2 > 1? Yes! Inversion found. count = 1.
  • j=3: arr[0]=2, arr[3]=3. Is 2 > 3? No. No inversion.
  • j=4: arr[0]=2, arr[4]=5. Is 2 > 5? No. No inversion.

Step 2: Fix i=1 (value 4). Compare with all elements after it.

  • j=2: arr[1]=4, arr[2]=1. Is 4 > 1? Yes! Inversion found. count = 2.
  • j=3: arr[1]=4, arr[3]=3. Is 4 > 3? Yes! Inversion found. count = 3.
  • j=4: arr[1]=4, arr[4]=5. Is 4 > 5? No. No inversion.

Step 3: Fix i=2 (value 1). Compare with all elements after it.

  • j=3: arr[2]=1, arr[3]=3. Is 1 > 3? No. No inversion.
  • j=4: arr[2]=1, arr[4]=5. Is 1 > 5? No. No inversion.

Step 4: Fix i=3 (value 3). Compare with all elements after it.

  • j=4: arr[3]=3, arr[4]=5. Is 3 > 5? No. No inversion.

Step 5: Return count = 3.

Brute Force — Checking All Pairs for Inversions — Watch how we compare every possible pair (i, j) where i < j, counting cases where the earlier element is larger than the later one.

Algorithm

  1. Initialize count = 0
  2. For each index i from 0 to n-2:
    • For each index j from i+1 to n-1:
      • If arr[i] > arr[j], increment count
  3. Return count

Code

#include <vector>
using namespace std;

class Solution {
public:
    int inversionCount(vector<int>& arr) {
        int n = arr.size();
        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++;
                }
            }
        }
        
        return count;
    }
};
class Solution:
    def inversionCount(self, arr: list[int]) -> int:
        n = len(arr)
        count = 0
        
        for i in range(n - 1):
            for j in range(i + 1, n):
                if arr[i] > arr[j]:
                    count += 1
        
        return count
class Solution {
    public int inversionCount(int[] arr) {
        int n = arr.length;
        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++;
                }
            }
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n-1 times, and for each i, the inner loop runs up to n-i-1 times. The total number of pairs checked is n×(n-1)/2, which is O(n²). For n = 10^5, this results in approximately 5 × 10^9 comparisons — far too slow for most competitive programming time limits.

Space Complexity: O(1)

We only use a single integer variable (count) for tracking. No extra data structures are needed.

Why This Approach Is Not Efficient

The brute force checks every possible pair, resulting in O(n²) time. With n up to 10^5, this means about 5 × 10^9 operations — well beyond the typical time limit of 10^8 operations per second.

The fundamental issue is that we are comparing each element with every element that comes after it independently, without reusing any information from previous comparisons. If we could somehow batch-count inversions instead of checking one pair at a time, we could dramatically speed things up.

The key insight comes from merge sort: when merging two sorted halves, if an element from the left half is greater than an element from the right half, then that left element is also greater than ALL remaining elements in the right half. This allows us to count multiple inversions at once instead of one pair at a time, bringing the complexity down to O(n log n).

Bar chart comparing O(n²) brute force vs O(n log n) merge sort for n=100,000
Bar chart comparing O(n²) brute force vs O(n log n) merge sort for n=100,000

Optimal Approach - Merge Sort

Intuition

The optimal approach cleverly piggybacks on the merge sort algorithm. Merge sort divides the array in half, recursively sorts each half, and then merges the two sorted halves. The key insight is that during the merge step, we can efficiently count cross-inversions — pairs where one element is in the left half and the other is in the right half.

Here is why this works: when we merge two sorted halves, we compare elements from the front of each half. If the current element from the left half (say left[i]) is greater than the current element from the right half (say right[j]), then left[i] is also greater than ALL remaining elements in the right half after right[j] — because the right half is already sorted in ascending order. This means we can count multiple inversions at once!

For example, if the left half is [3, 5, 7] and the right half is [2, 4, 6], when we see that left[0]=3 > right[0]=2, we know that 5 and 7 (which are after 3 in the left half) are also greater than 2. So we count 3 inversions at once (one for each remaining element in the left half, including the current one).

The total inversions equal: inversions within left half + inversions within right half + cross-inversions (counted during merge). The recursive structure of merge sort handles the first two automatically, and we add the cross-inversion counting to the merge step.

Step-by-Step Explanation

Let's trace through the merge step with left = [2, 4] and right = [1, 3] (these are already-sorted halves from merging arr = [2, 4, 1, 3]):

Step 1: Initialize pointers: i=0 (left), j=0 (right), merged result = []. Cross-inversions = 0. Left has 2 remaining elements.

Step 2: Compare left[0]=2 with right[0]=1. Since 2 > 1, right[0] is smaller than ALL remaining left elements (2 and 4). Count inversions: 2 (the number of remaining elements in the left half). Cross-inversions = 2. Place 1 into merged. merged = [1]. Advance j.

Step 3: Compare left[0]=2 with right[1]=3. Since 2 ≤ 3, no inversion. Place 2 into merged. merged = [1, 2]. Advance i. Left has 1 remaining element.

Step 4: Compare left[1]=4 with right[1]=3. Since 4 > 3, right[1] is smaller than ALL remaining left elements (just 4). Count inversions: 1. Cross-inversions = 3. Place 3 into merged. merged = [1, 2, 3]. Advance j.

Step 5: Right half exhausted. Copy remaining left element. Place 4 into merged. merged = [1, 2, 3, 4].

Step 6: This merge step contributed 3 cross-inversions. Combined with inversions from recursive calls on each half, we get the total.

Merge Sort — Counting Inversions During the Merge Step — Watch how during the merge of two sorted halves, whenever a right element is smaller than the current left element, we count all remaining left elements as inversions at once — this is the key to O(n log n) efficiency.

Algorithm

  1. mergeSort(arr, left, right):

    • If left >= right, return 0 (base case: single element has no inversions)
    • Find mid = (left + right) / 2
    • count = mergeSort(arr, left, mid) — inversions in left half
    • count += mergeSort(arr, mid + 1, right) — inversions in right half
    • count += merge(arr, left, mid, right) — cross-inversions during merge
    • Return count

  2. merge(arr, left, mid, right):

    • Create temporary arrays for left half and right half
    • Initialize pointers i=0, j=0, k=left, inversions=0
    • While both halves have elements:
      • If leftArr[i] ≤ rightArr[j]: place leftArr[i] into arr[k], advance i
      • Else: place rightArr[j] into arr[k], advance j, add (mid - left + 1 - i) to inversions (all remaining left elements form inversions with rightArr[j])
    • Copy any remaining elements from either half
    • Return inversions

Code

#include <vector>
using namespace std;

class Solution {
public:
    int merge(vector<int>& arr, int left, int mid, int right) {
        vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
        vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);
        
        int i = 0, j = 0, k = left;
        int inversions = 0;
        int leftSize = mid - left + 1;
        
        while (i < leftSize && j < (int)rightArr.size()) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                // All remaining elements in left half are > rightArr[j]
                inversions += (leftSize - i);
                arr[k++] = rightArr[j++];
            }
        }
        
        while (i < leftSize) {
            arr[k++] = leftArr[i++];
        }
        while (j < (int)rightArr.size()) {
            arr[k++] = rightArr[j++];
        }
        
        return inversions;
    }
    
    int mergeSort(vector<int>& arr, int left, int right) {
        if (left >= right) return 0;
        
        int mid = left + (right - left) / 2;
        int count = 0;
        
        count += mergeSort(arr, left, mid);
        count += mergeSort(arr, mid + 1, right);
        count += merge(arr, left, mid, right);
        
        return count;
    }
    
    int inversionCount(vector<int>& arr) {
        return mergeSort(arr, 0, arr.size() - 1);
    }
};
class Solution:
    def inversionCount(self, arr: list[int]) -> int:
        
        def merge(arr: list[int], left: int, mid: int, right: int) -> int:
            left_arr = arr[left:mid + 1]
            right_arr = arr[mid + 1:right + 1]
            
            i = 0
            j = 0
            k = left
            inversions = 0
            left_size = len(left_arr)
            
            while i < left_size and j < len(right_arr):
                if left_arr[i] <= right_arr[j]:
                    arr[k] = left_arr[i]
                    i += 1
                else:
                    # All remaining left elements are > right_arr[j]
                    inversions += (left_size - i)
                    arr[k] = right_arr[j]
                    j += 1
                k += 1
            
            while i < left_size:
                arr[k] = left_arr[i]
                i += 1
                k += 1
            while j < len(right_arr):
                arr[k] = right_arr[j]
                j += 1
                k += 1
            
            return inversions
        
        def merge_sort(arr: list[int], left: int, right: int) -> int:
            if left >= right:
                return 0
            
            mid = (left + right) // 2
            count = 0
            
            count += merge_sort(arr, left, mid)
            count += merge_sort(arr, mid + 1, right)
            count += merge(arr, left, mid, right)
            
            return count
        
        return merge_sort(arr, 0, len(arr) - 1)
class Solution {
    public int inversionCount(int[] arr) {
        return mergeSort(arr, 0, arr.length - 1);
    }
    
    private int mergeSort(int[] arr, int left, int right) {
        if (left >= right) return 0;
        
        int mid = left + (right - left) / 2;
        int count = 0;
        
        count += mergeSort(arr, left, mid);
        count += mergeSort(arr, mid + 1, right);
        count += merge(arr, left, mid, right);
        
        return count;
    }
    
    private int merge(int[] arr, int left, int mid, int right) {
        int[] leftArr = new int[mid - left + 1];
        int[] rightArr = new int[right - mid];
        
        for (int i = 0; i < leftArr.length; i++)
            leftArr[i] = arr[left + i];
        for (int j = 0; j < rightArr.length; j++)
            rightArr[j] = arr[mid + 1 + j];
        
        int i = 0, j = 0, k = left;
        int inversions = 0;
        int leftSize = leftArr.length;
        
        while (i < leftSize && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                // All remaining left elements form inversions
                inversions += (leftSize - i);
                arr[k++] = rightArr[j++];
            }
        }
        
        while (i < leftSize) arr[k++] = leftArr[i++];
        while (j < rightArr.length) arr[k++] = rightArr[j++];
        
        return inversions;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

This is the same time complexity as merge sort itself. The array is recursively divided into halves log n times, and at each level of recursion, the merge step processes all n elements exactly once. The inversion counting during merge adds only O(1) extra work per comparison (just an addition operation), so the overall time remains O(n log n). For n = 10^5, this is about 1.7 × 10^6 operations — extremely fast.

Space Complexity: O(n)

The merge step requires temporary arrays to hold the left and right halves. At any point during the recursion, the total extra space used is proportional to the size of the array being merged, which is O(n) in the worst case. Additionally, the recursion stack depth is O(log n), which is dominated by the O(n) temporary array space.