Count Inversions
A medium Sorting interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sorting
- Sheets
- 2
- Core for
- 13 roles
The problem
Given an array of integers, count the number of pairs (i, j) where i < j and nums[i] > nums[j].
Example 1
- Input
- nums = [4, 1, 3, 2, 4]
- Output
- 4
- Why
- The out-of-order pairs are (4,1), (4,3), (4,2) and (3,2).
Example 2
- Input
- nums = [3, 5, 2, 4, 6]
- Output
- 3
- Why
- The out-of-order pairs are (3,2), (5,2) and (5,4).
Constraints
- 1 <= nums.length <= 5 * 10^4
- -10^5 <= nums[i] <= 10^5
How to think about it
Updated 2026-09-29An inversion measures how out of order two values are. Notice that during merge sort, both halves are already individually sorted. When an element from the right half is smaller than the current element in the left half, it is automatically smaller than every remaining element in that left half, allowing hundreds of inversions to be tallied in a single addition.
Approaches, worst first
All pairs check
time O(n^2) · space O(1)
Compare every pair (i, j) with i < j using two nested loops and increment a counter whenever nums[i] > nums[j]. Exhaustive and straightforward, but quadratic runtime is far too slow for 50,000 elements.
Enhanced merge sort
time O(n log n) · space O(n)
Divide into halves recursively, sum inversions found within each half, and add cross-inversions during the merge step. When right element nums[j] is chosen before nums[i], add `mid - i + 1` to the total in O(1) time.
Fenwick tree with coordinate compressionWrite this one
time O(n log n) · space O(n)
Map values to ranks, then traverse backward inserting ranks into a Binary Indexed Tree while querying the count of already inserted elements with smaller rank. Matches merge sort time complexity and processes elements in an online stream.
Where people lose marks · 3
- Integer overflow: with n = 50,000, the maximum number of inversions is n * (n - 1) / 2, which exceeds 1.2 * 10^9 and can overflow 32-bit signed integers if intermediate sums double.
- Counting `mid - i` instead of `mid - i + 1`: since the left subarray spans indices i through mid inclusive, the count of remaining larger elements must include index mid.
- Treated equal elements as inversions: when `nums[i] == nums[j]`, they are not out of order; the merge must pull from the left half without adding to the inversion count.
Full solution
C++
#include <bits/stdc++.h>
using namespace std;
static long long merge_count(vector<int>& arr, int lo, int hi, vector<int>& tmp) {
if (lo >= hi) return 0;
int mid = lo + (hi - lo) / 2;
long long count = merge_count(arr, lo, mid, tmp) + merge_count(arr, mid + 1, hi, tmp);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
count += (mid - i + 1);
}
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= hi) tmp[k++] = arr[j++];
for (int p = lo; p <= hi; p++) arr[p] = tmp[p];
return count;
}
int inversionCount(vector<int>& arr) {
if (arr.size() < 2) return 0;
vector<int> tmp(arr.size());
return (int)merge_count(arr, 0, (int)arr.size() - 1, tmp);
}
Java
import java.util.*;
public class Main {
private static long mergeCount(int[] arr, int lo, int hi, int[] tmp) {
if (lo >= hi) return 0;
int mid = lo + (hi - lo) / 2;
long count = mergeCount(arr, lo, mid, tmp) + mergeCount(arr, mid + 1, hi, tmp);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
count += (mid - i + 1);
}
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= hi) tmp[k++] = arr[j++];
for (int p = lo; p <= hi; p++) arr[p] = tmp[p];
return count;
}
static int inversionCount(int[] arr) {
if (arr.length < 2) return 0;
int[] tmp = new int[arr.length];
return (int) mergeCount(arr, 0, arr.length - 1, tmp);
}
}
Python
def inversion_count(arr):
values = list(arr)
def sort_count(items):
if len(items) < 2: return items, 0
mid = len(items) // 2
left, a = sort_count(items[:mid]); right, b = sort_count(items[mid:])
merged = []; i = j = 0; count = a + b
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1; count += len(left) - i
return merged + left[i:] + right[j:], count
return sort_count(values)[1]
JavaScript
function inversionCount(arr) {
const values = [...arr]; let count = 0;
for (let i = 0; i < values.length; i++) for (let j = i + 1; j < values.length; j++) if (values[i] > values[j]) count++;
return count;
}
The theory behind it
Sorting — the ground this problem stands on. All Sorting problems
What Sorting is
Sorting is the act of arranging a scrambled hand of playing cards into ascending rank from left to right. It reorganizes scattered data according to a consistent comparison rule, like numbering index cards or alphabetizing names. While unsorted data requires searching every single entry to verify whether an item exists, ordered data establishes predictable relationships that make duplicates, clusters, and extreme values immediately visible.
When to reach for it
Reach for sorting when a problem asks to group identical items, detect overlaps among intervals, find rank percentiles, or pair values matching a target sum. If an unordered problem appears intractable in polynomial time, sorting the input frequently unlocks linear scans or two-pointer sweeps. When an O(n log n) preprocessing step simplifies downstream matching logic, sorting is usually the right opening move.
How the pattern works
Think of sorting as a trade: invest logarithmic overhead upfront to make subsequent queries direct and orderly. Compare adjacent elements to uncover duplicate entries, or march inward from outer boundaries once elements stand in monotonic sequence. When designing custom comparators, confirm strict weak ordering by verifying reflexivity, antisymmetry, and transitivity; inconsistent comparison logic breaks internal pivot partitions or produces corrupted outputs.
More Sorting problems
Target Roles
Core requirement for 13 roles:
Asked at
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .