Log inSign up
hardGeeksforGeeksNot Started

Count Inversions

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer array arr, return the inversion count of the array.

The inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted, the inversion count is 0. If the array is sorted in reverse order, the inversion count is maximal: N * (N - 1) / 2.

Formally, two elements arr[i] and arr[j] form an inversion if arr[i] > arr[j] and i < j.

Example 1 · Standard Inversion Example:

Input: arr = [2, 4, 1, 3, 5]
Output: 3
Explanation: The 3 inversion pairs are (2, 1), (4, 1), and (4, 3).

Example 2 · Already Sorted Array:

Input: arr = [1, 2, 3, 4, 5]
Output: 0
Explanation: No element is greater than any subsequent element.

Example 3 · Reverse Sorted Array:

Input: arr = [5, 4, 3, 2, 1]
Output: 10
Explanation: Total pairs = 5 * 4 / 2 = 10 inversions.

Constraints:

  • 1 <= arr.length <= 105
  • -109 <= arr[i] <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Standard Merge Sort divide-and-conquer implementation
  • Two-pointer merge subroutine for two sorted arrays
  • Integer overflow considerations for inversion counts (use 64-bit integers)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master divide-and-conquer split counting mechanics during array merging.
  • Understand why mid - i + 1 counts all remaining left subarray inversions in O(1).
  • Prevent 32-bit integer overflow when accumulating up to N*(N-1)/2 inversions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting pairs (i, j) where i < j and arr[i] > arr[j].
  • Measuring sortedness / distance from sorted order.
  • Global inversion / local inversion counting queries.

Algorithmic Decision Tree:

  • Use Enhanced Merge Sort divide-and-conquer to count split inversions in O(N log N).
  • Alternatively, use Fenwick Tree / Binary Indexed Tree with coordinate compression for online stream updates.

Connected Patterns:

Global and Local Inversions (LeetCode 775)Reverse Pairs (LeetCode 493)Count of Smaller Numbers After Self (LeetCode 315)

1. Nested Double Loop Comparison

Intuition

Exhaustively check every possible pair to verify the inversion condition.

Algorithm

  1. Step 1: Initialize inversion counter = 0.
  2. Step 2: Loop i from 0 to n - 2.
  3. Step 3: Loop j from i + 1 to n - 1.
  4. Step 4: If arr[i] > arr[j], increment counter by 1.
  5. Step 5: Return counter.

Nested Double Loop Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 4, 1, 3, 5]
Current operationSTEP 1 OF 6
Input arr = [2, 4, 1, 3, 5]
Visual state
Values and pointers at this exact step
pointers
S
2
4
1
3
5
0
↑ i=0
1
2
3
4
Variables at this step
i
0
val
2
inversions
0
Check / comparison
i = 0, arr[0] = 2
Decision / next transition
Compare arr[0] with j = 1..4.
Why this step matters

Input arr = [2, 4, 1, 3, 5]. Initialize inversions = 0. Start outer loop i = 0 (val = 2).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 long long countInversions(const std::vector<int>& arr) {
7 long long count = 0;
8 int n = arr.size();
9 for (int i = 0; i < n - 1; ++i) {
10 for (int j = i + 1; j < n; ++j) {
11 if (arr[i] > arr[j]) {
12 count++;
13 }
14 }
15 }
16 return count;
17 }
18};
19
20int main() {
21 Solution solver;
22 std::vector<int> arr = {2, 4, 1, 3, 5};
23 std::cout << "Inversions: " << solver.countInversions(arr) << std::endl; // 3
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Nested Double Loop Comparison.
  • Space complexity: O(1) — Space complexity for Nested Double Loop Comparison.

Why Brute Force Doesn't Scale:

For N = 100,000, N2 = 1010 operations, which times out.

Merge Sort Count completes in ~1.7 * 106 operations, executing in ~25 milliseconds.

2. Fenwick Tree (Binary Indexed Tree)

Intuition

Insert elements into a frequency Fenwick Tree from right to left while querying prefix sums.

Algorithm

  1. Step 1: Coordinate compress unique elements into ranks 1 to K.
  2. Step 2: Allocate BIT of size K initialized to 0.
  3. Step 3: Traverse arr from right to left: query sum(rank - 1) to count smaller elements already seen.
  4. Step 4: Add result to total inversion count, then update BIT at position rank by +1.
  5. Step 5: Return total count.

Fenwick Tree (Binary Indexed Tree) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 4, 1, 3, 5]
Current operationSTEP 1 OF 6
Allocate Fenwick Tree BIT of size 6 initialized to 0
Visual state
Values and pointers at this exact step
pointers
S
5
0
↑ val=5
Variables at this step
i
4
val
5
inversions
0
Check / comparison
Initialize BIT
Decision / next transition
At index 4 (val = 5): query(4) = 0. inversions += 0. add(5, 1).
Why this step matters

Allocate Fenwick Tree BIT of size 6 initialized to 0. Traverse arr = [2, 4, 1, 3, 5] backwards from right to left.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class BIT {
6 int size;
7 std::vector<int> tree;
8public:
9 BIT(int n) : size(n), tree(n + 1, 0) {}
10 void update(int idx, int val) {
11 for (; idx <= size; idx += idx & -idx) tree[idx] += val;
12 }
13 long long query(int idx) {
14 long long sum = 0;
15 for (; idx > 0; idx -= idx & -idx) sum += tree[idx];
16 return sum;
17 }
18};
19
20class Solution {
21public:
22 long long countInversions(std::vector<int>& arr) {
23 int n = arr.size();
24 std::vector<int> sorted = arr;
25 std::sort(sorted.begin(), sorted.end());
26 sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
27
28 BIT bit(sorted.size());
29 long long inversions = 0;
30
31 for (int i = n - 1; i >= 0; --i) {
32 int rank = std::lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin() + 1;
33 inversions += bit.query(rank - 1);
34 bit.update(rank, 1);
35 }
36 return inversions;
37 }
38};
39
40int main() {
41 Solution solver;
42 std::vector<int> arr = {2, 4, 1, 3, 5};
43 std::cout << "BIT Inversions: " << solver.countInversions(arr) << std::endl; // 3
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Fenwick Tree (Binary Indexed Tree).
  • Space complexity: O(N) — Space complexity for Fenwick Tree (Binary Indexed Tree).

3. Enhanced Merge Sort Divide and Conquer

Intuition

Because left half is sorted, if right element < left[i], then right element is smaller than all remaining elements in left half.

Algorithm

  1. Step 1: Divide array at mid = (low + high) / 2.
  2. Step 2: Recursively count inversions in left half: invCount += mergeSortCount(low, mid).
  3. Step 3: Recursively count inversions in right half: invCount += mergeSortCount(mid + 1, high).
  4. Step 4: In merge step: if right[j] < left[i], add (mid - i + 1) to count and insert right[j] into buffer.
  5. Step 5: Copy merged buffer back into original array and return total inversion count.

Enhanced Merge Sort Divide and Conquer Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [Left: [2, 4], Right: [1, 3, 5], mid=1]
Current operationSTEP 1 OF 6
Divide arr = [2, 4, 1, 3, 5] into Left = [2, 4] and Right = [1, 3, 5]
Visual state
Values and pointers at this exact step
pointers
S
2
4
1
3
5
0
↑ Left
1
2
↑ Right
3
4
Variables at this step
left
[2,4]
right
[1,3,5]
inversions
0
Check / comparison
Split at mid = 1
Decision / next transition
Recursively sort Left and Right subarrays.
Why this step matters

Divide arr = [2, 4, 1, 3, 5] into Left = [2, 4] and Right = [1, 3, 5]. mid index = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 long long merge(std::vector<int>& arr, std::vector<int>& temp, int low, int mid, int high) {
6 int i = low; // Left subarray pointer
7 int j = mid + 1; // Right subarray pointer
8 int k = low; // Buffer pointer
9 long long invCount = 0;
10
11 while (i <= mid && j <= high) {
12 if (arr[i] <= arr[j]) {
13 temp[k++] = arr[i++];
14 } else {
15 temp[k++] = arr[j++];
16 invCount += (mid - i + 1); // Key observation!
17 }
18 }
19
20 while (i <= mid) temp[k++] = arr[i++];
21 while (j <= high) temp[k++] = arr[j++];
22
23 for (int idx = low; idx <= high; ++idx) {
24 arr[idx] = temp[idx];
25 }
26
27 return invCount;
28 }
29
30 long long mergeSortAndCount(std::vector<int>& arr, std::vector<int>& temp, int low, int high) {
31 long long invCount = 0;
32 if (low < high) {
33 int mid = low + (high - low) / 2;
34 invCount += mergeSortAndCount(arr, temp, low, mid);
35 invCount += mergeSortAndCount(arr, temp, mid + 1, high);
36 invCount += merge(arr, temp, low, mid, high);
37 }
38 return invCount;
39 }
40
41public:
42 long long countInversions(std::vector<int>& arr) {
43 int n = arr.size();
44 if (n <= 1) return 0;
45 std::vector<int> temp(n);
46 return mergeSortAndCount(arr, temp, 0, n - 1);
47 }
48};
49
50int main() {
51 Solution solver;
52 std::vector<int> arr = {2, 4, 1, 3, 5};
53 std::cout << "Optimal Merge Sort Inversions: " << solver.countInversions(arr) << std::endl; // 3
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Enhanced Merge Sort Divide and Conquer.
  • Space complexity: O(N) — Space complexity for Enhanced Merge Sort Divide and Conquer.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Nested Pairwise LoopO(N^2)O(1)Compare every pair (i, j) with i < j and increment count if arr[i] > arr[j].Inspects N*(N-1)/2 pairs individually.
2.Better — Fenwick Tree (Binary Indexed Tree)O(N log N)O(N)Coordinate compress array values, insert from right to left while querying prefix sums.BIT rank conversions.
3.Optimal — Enhanced Merge SortOptimalO(N log N)O(N)Divide array into halves, sort and count left/right recursively, then count split inversions (mid - i + 1) during the merge pass.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Array already sorted in ascending order ([1, 2, 3]) — Returns 0 inversions.
  • Array reverse sorted ([5, 4, 3, 2, 1]) — Returns maximum N*(N-1)/2 = 10 inversions.
  • Array with duplicate elements ([2, 2, 2]) — Condition arr[i] <= arr[j] ensures duplicates do not count as inversions.
  • Single element array ([10]) — Returns 0 immediately in O(1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the merge step add (mid - i + 1) inversions when arr[j] < arr[i]?

2.What is the maximum possible number of inversions in an array of size N?

3.Why can the total inversion count exceed a standard 32-bit integer in C++ and Java?

Back to DSA Sheet