AlgoViz
HomeArrays & Hashing

Count Inversions

Hard

Count across the merge step

Problem

Given an integer array nums. Return the number of inversions in the array. Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. It indicates how close an array is to being sorted. A sorted array has an inversion count of 0. An array sorted in descending order has maximum inversion.

In simple words

Count pairs where a bigger number sits before a smaller one — merge sort tallies these fast.

The idea

Run merge sort, and when the right half supplies the smaller element, every element remaining in the left half forms an inversion with it. Counting them in bulk during the merge gives O(n log n) instead of checking all pairs.

The trick

  • When right[j] < left[i], add (mid - i + 1) inversions at once.
  • Do the counting during the merge, not after — the halves are sorted by then.
  • O(n log n) time, O(n) space.
2
4
1
3
5
0
1
2
3
4

Step 1 of 12. Brute force: check every pair where a bigger number sits before a smaller one. Values: 2, 4, 1, 3, 5.

1/12
Brute force
timeO(n²)spaceO(1)

Every pair.

1for (let i = 0; i < n; i++)2  for (let j = i + 1; j < n; j++)3    if (nums[i] > nums[j]) count++;4return count;

Input

array
[2, 4, 1, 3, 5]

Memory

i
—
j
—

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [2, 4, 1, 3, 5]
Output:
3
Explanation:
3 pairs are out of order.

Example 2

Input:
nums = [5, 4, 3, 2, 1]
Output:
10
Explanation:
Fully reversed → 10 inversions.

Example 3

Input:
nums = [1, 2, 3]
Output:
0
Explanation:
Already sorted → 0.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.