Count inversions in a price series

Question

An inversion is a pair of positions i < j where prices[i] prices[j], an earlier price that is higher than a later one. The inversion count measures how far a series is from sorted ascending. Count them. Return the number of inversions. Aim for O(n \log n).

Accepted Answer

Piggyback on merge sort. Recursively sort and count each half, then count cross inversions during the merge: when an element from the right half is placed before remaining elements of the (sorted) left half, every one of those remaining left elements is larger, so they each form an inversion with it. Add all three counts. Tracing [3, 1, 2]: the merges surface the pairs (3, 1) and (3, 2), so the count is 2. Time O(n \log n), space O(n) for the merge buffers. The <= comparison keeps equal values from counting as inversions; the key insight is that len(left) - i counts all still-unmerged left el…

Count inversions in a price series

Your answer

More Coding questions