Count Inversions

Q: What is an inversion in an array?

An inversion is a pair of positions i < j where nums[i] > nums[j] , so a larger value sits before a smaller one. A sorted list has 0 inversions, and a reversed list of distinct values has the most, n(n-1)/2 . The count equals the number of neighbour swaps bubble sort makes.

Q: What is the time complexity of counting inversions with merge sort?

O(n log n) time and O(n) extra space for the merge buffer. Each of the log n levels of merging touches every value once, about 3 × 10^5 steps for 2 × 10^4 values. The pair-by-pair loop is O(n²) .

MediumSorting Recursion

+10

Given a list of integers nums, return the number of inversions: pairs of indexes i < j with nums[i] > nums[j], a larger value before a smaller one. Equal values never form an inversion, and a sorted list has none.

Function

countInversions(nums: integer-array) → integer

numsinteger-array: the list of integers
Returnsinteger: the number of pairs i < j with nums[i] > nums[j]

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
The answer is at most n(n-1)/2 < 2 × 10⁸, so it fits in a signed 32-bit integer.

Examples

Input: nums = [5, 3, 8, 1, 4]
Output: 6
Explanation: 5 comes before 3, 1 and 4: 3 pairs. 3 comes before 1, and 8 before 1 and 4: 3 more. 1 and 4 are in order, so the total is 6.

Follow-up

What changes if a pair only counts when nums[i] > 2 × nums[j]? Can merge sort still count those pairs in O(n log n)?

Solution

Checking every pair takes about n² / 2 comparisons. Merge sort counts pairs in bulk: when a value from the right half is placed during a merge, every left value still waiting is larger and came before it. One subtraction counts that whole batch, so counting costs nothing beyond the O(n log n) sort.

Check every pair

Correct, but does not finish on the largest tests

Intuition

For every index i, check every later index j and add 1 when nums[i] > nums[j]. That is the definition, and the strict comparison leaves equal values out.

The cost is n(n-1)/2 comparisons: almost 2 × 10^8 for 2 × 10^4 values, and doubling n makes it four times larger.

Algorithm

Set count = 0.
For each i from 0 to n-1, and each j from i + 1 to n-1, add 1 to count when nums[i] > nums[j].
Return count.

def countInversions(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                count += 1
    return count

Merge sort that counts while merging

Intuition

Split the list at the middle. An inversion has both values in the left half, both in the right half, or one on each side. Recursing on each half counts the first two kinds and sorts that half. Sorting moves values only within a half, so every left value still comes before every right value, and the crossing pairs are unchanged.

In the merge, if left[i] ≤ right[j], place left[i]: every right value still waiting is at least right[j], so it forms no inversion. Otherwise right[j] is smaller than left[i] and, the left half being sorted, smaller than every left value still waiting. Add their number. Placing the left value on a tie keeps equal values out.

On [5, 3, 8, 1, 4] the halves hold 1 and 2 inversions. Merging [3, 5] with [1, 4, 8], 1 passes 3 and 5 and 4 passes 5: 1 + 2 + 3 = 6.

Algorithm

Copy nums and make a buffer of the same length.
To sort and count a range of fewer than 2 values, return 0.
Otherwise split it at mid and sort and count each half.
Merge the halves through the buffer: on left[i] ≤ right[j] take the left value; otherwise take the right value and add the number of left values not yet placed.
Copy the merged range back and return the three counts added together.

def sortAndCount(a, buf, lo, hi):
    # Sorts a[lo:hi] and returns the number of inversions inside it.
    if hi - lo < 2:
        return 0
    mid = (lo + hi) // 2
    count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
    # Merge the two sorted halves, counting the pairs that cross the middle.
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            # a[j] is smaller than every left value not placed yet: a[i..mid-1].
            buf[k] = a[j]
            j += 1
            count += mid - i
        k += 1
    while i < mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        buf[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = buf[lo:hi]
    return count


def countInversions(nums):
    a = list(nums)  # sort a copy, not the caller's list
    return sortAndCount(a, [0] * len(a), 0, len(a))

Pitfalls and edge cases

Adding 1 when a right value is placed. It passes every left value still waiting, so add their number, mid - i.
Taking the right value on a tie, with left[i] < right[j] as the test for the left side. Then [2, 2, 2, 1] counts the equal 2s against each other and returns more than 3. Use ≤.
Counting while copying the leftovers after one half runs out. Leftover left values have no right value after them, and leftover right values were already compared with every left value.

Frequently asked questions3

What is an inversion in an array?

An inversion is a pair of positions i < j where nums[i] > nums[j], so a larger value sits before a smaller one. A sorted list has 0 inversions, and a reversed list of distinct values has the most, n(n-1)/2. The count equals the number of neighbour swaps bubble sort makes.

What is the time complexity of counting inversions with merge sort?

O(n log n) time and O(n) extra space for the merge buffer. Each of the log n levels of merging touches every value once, about 3 × 10^5 steps for 2 × 10^4 values. The pair-by-pair loop is O(n²).

Can inversions be counted without merge sort?

Yes. A Fenwick tree (binary indexed tree) over the ranks of the values walks the list once and, for each value, asks how many earlier values are larger, in O(log n) per value. That is also O(n log n) in total. A balanced search tree that tracks subtree sizes works the same way.

def countInversions(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [5, 3, 8, 1, 4]

Expected Output