Count inversions in a permutation
Company: Hudson River Trading
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Given an array `a` of length `n` that is a permutation of distinct integers (e.g., `1..n`), define an **inversion** as a pair of indices `(i, j)` such that:
- `0 ≤ i < j < n`, and
- `a[i] > a[j]`.
### Task
Write a function that returns the number of inversions in the array.
### Input/Output
- **Input:** an integer array `a` with all distinct values
- **Output:** a single integer = the number of inversions
### Notes
- Any time complexity is acceptable (e.g., an `O(n^2)` approach is fine), but you may also discuss faster approaches if you know them.
Overview: This question evaluates understanding of inversion counting in permutations, testing algorithmic problem-solving, complexity analysis, and data-structure reasoning about pairwise order relations.
Given a list of distinct integers, return the number of pairs i < j with a[i] > a[j].
Constraints
- All values are distinct.
- 0 <= len(a) <= 200000
Examples
Input: ([1, 2, 3, 4],)
Expected Output: 0
Explanation: Already sorted has no inversions.
Input: ([4, 3, 2, 1],)
Expected Output: 6
Explanation: Reverse sorted has every pair inverted.
Hints
- A merge-sort count adds the number of remaining left elements when taking from the right.