Count Inversions — Solution in Python, Java & C++
Count Inversions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Inversions is a medium coding problem on arrays, divide and conquer and binary indexed tree, asked in Amazon, Microsoft, Flipkart and Myntra interviews.
- Difficulty: Medium
- Topics: Arrays, Divide and Conquer, Binary Indexed Tree
- Asked at: Amazon, Microsoft, Flipkart, Myntra
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An inversion is a pair of indices (i, j) with i < j and arr[i] > arr[j] — a pair that is out of order.
The inversion count measures how far an array is from being sorted: a sorted array has 0, and a strictly decreasing array has the maximum possible.
Given arr, return its inversion count.
Example 1
Input: arr = [2,4,1,3,5]
Output: 3
Explanation: The out-of-order pairs are (2,1), (4,1) and (4,3).
Example 2
Input: arr = [2,3,4,5,6]
Output: 0
Explanation: Already sorted.
Example 3
Input: arr = [10,10,10]
Output: 0
Explanation: Equal values are not inversions — the comparison is strict.
Constraints
1 <= arr.length <= 10001 <= arr[i] <= 1000
Hints for Count Inversions
Hint 1
The brute-force double loop is O(n²). The interview wants O(n log n).
Hint 2
Process left to right and ask: how many values already placed are strictly greater than the current one?
Hint 3
A Fenwick (binary indexed) tree over the value range answers that in
logtime. Merge sort is the other standard route.
How to solve Count Inversions
Sweep left to right keeping a frequency structure over values already seen. For the current x, the number of earlier values strictly greater than x is seen - (count of values <= x), and a Fenwick tree gives that prefix count in O(log V).
Approach
- Create a Fenwick tree over the value range
1 .. 1000, all zeros. - For each element
xin order: addseen - query(x)to the answer, wherequery(x)counts already-inserted values<= x. - Insert
xinto the tree and incrementseen.
Why it works
Every inversion (i, j) is counted exactly once — at the moment j is processed, because arr[i] is already in the tree and arr[i] > arr[j] is exactly what seen - query(arr[j]) measures.
Complexity
- Time —
O(n log V) - Space —
O(V)
Pitfalls
- Using
query(x)alone counts values<= x, which includes ties; the strict comparison is why the subtraction is fromseen. - A Fenwick tree is 1-indexed — a value of
0would loop forever in the update, so the values here start at 1.
Reference solution
Python
from typing import List
def countInversions(arr: List[int]) -> int:
MAX = 1001
bit = [0] * (MAX + 1)
def add(i: int) -> None:
while i <= MAX:
bit[i] += 1
i += i & -i
def pref(i: int) -> int:
s = 0
while i > 0:
s += bit[i]
i -= i & -i
return s
total = 0
seen = 0
for x in arr:
total += seen - pref(x)
add(x)
seen += 1
return totalJava
public static int countInversions(int[] arr) {
final int MAX = 1001;
int[] bit = new int[MAX + 1];
int total = 0, seen = 0;
for (int x : arr) {
int s = 0;
for (int p = x; p > 0; p -= p & -p) s += bit[p];
total += seen - s;
for (int q = x; q <= MAX; q += q & -q) bit[q]++;
seen++;
}
return total;
}C++
int countInversions(vector<int>& arr) {
const int MAXV = 1001;
vector<int> bit(MAXV + 1, 0);
int total = 0, seen = 0;
for (int x : arr) {
int s = 0;
for (int p = x; p > 0; p -= p & -p) s += bit[p];
total += seen - s;
for (int q = x; q <= MAXV; q += q & -q) bit[q]++;
seen++;
}
return total;
}JavaScript
var countInversions = function(arr) {
var MAX = 1001;
var bit = [];
for (var t = 0; t <= MAX; t++) bit.push(0);
var total = 0, seen = 0;
for (var i = 0; i < arr.length; i++) {
var x = arr[i];
var s = 0;
for (var p = x; p > 0; p -= p & -p) s += bit[p];
total += seen - s;
for (var q = x; q <= MAX; q += q & -q) bit[q]++;
seen++;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays