Practice › Arrays
Count Inversions
Hard · Arrays · Asked at Amazon, Microsoft, Google, Flipkart
An inversion is a pair (i, j) with i < j and a[i] > a[j]. Count the inversions.
Input
First line: n. Second line: n space-separated integers.
Output
The number of inversions.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ a[i] ≤ 10^9
O(n²) is too slow for n = 10^5 — count inversions while doing merge sort. The answer can exceed 32-bit range.
Example 1
Input
5 2 4 1 3 5
Output
3
Example 2
Input
3 1 2 3
Output
0
Hints
- An inversion is a pair i < j with a[i] > a[j]. Checking all pairs is O(n²).
- Merge sort: while merging, if right[j] < left[i], then right[j] is smaller than every remaining left element.
Approach
Sort with merge sort and count during each merge. Both halves are sorted, so when the right element b[j] is taken before the left element a[i], it forms an inversion with a[i] and with every element after it in the left half: add (leftSize − i). Take from the left when the values are equal, because equal values aren't inversions. The total can reach about n²/2 ≈ 5 × 10^9, so use a 64-bit counter.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
long long sortCount(vector<long long> &a, vector<long long> &tmp, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) / 2;
long long cnt = sortCount(a, tmp, lo, mid) + sortCount(a, tmp, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else {
cnt += mid - i;
tmp[k++] = a[j++];
}
}
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (int t = lo; t < hi; t++) a[t] = tmp[t];
return cnt;
}
int main() {
int n;
cin >> n;
vector<long long> a(n), tmp(n);
for (auto &x : a) cin >> x;
cout << sortCount(a, tmp, 0, n) << "\n";
return 0;
}Python solution
import sys
def sort_count(a):
if len(a) <= 1:
return a, 0
mid = len(a) // 2
left, x = sort_count(a[:mid])
right, y = sort_count(a[mid:])
merged, cnt, i, j = [], x + y, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
cnt += len(left) - i
merged.append(right[j])
j += 1
merged += left[i:]
merged += right[j:]
return merged, cnt
data = list(map(int, sys.stdin.read().split()))
print(sort_count(data[1 : data[0] + 1])[1])Java solution
import java.util.*;
public class Main {
static long[] a, tmp;
static long sortCount(int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) / 2;
long cnt = sortCount(lo, mid) + sortCount(mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else {
cnt += mid - i;
tmp[k++] = a[j++];
}
}
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
System.arraycopy(tmp, lo, a, lo, hi - lo);
return cnt;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
a = new long[n];
tmp = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
System.out.println(sortCount(0, n));
}
}