Count inversions in an array efficiently
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given the array [5, 7, 9, 2, 3, 12, 8, 4], compute the number of inversion pairs (i, j) where i < j and arr[i] > arr[j]. Describe both a naive O(n^
2) approach and an O(n log n) divide-and-conquer method, and analyze their complexities.
Quick Answer: This question evaluates understanding of inversion counting and algorithmic design, specifically comparing naive O(n^2) approaches with O(n log n) divide-and-conquer strategies while requiring analysis of time and space complexity.
Given an integer array `arr`, count the number of inversion pairs `(i, j)` such that `i < j` and `arr[i] > arr[j]`.
An inversion measures how far the array is from being sorted in ascending order: a sorted array has 0 inversions, and a strictly descending array of length n has the maximum n*(n-1)/2 inversions.
For example, given `[5, 7, 9, 2, 3, 12, 8, 4]`, the answer is `13`.
The naive approach checks every pair in O(n^2) time. The efficient approach augments merge sort: while merging two sorted halves, every time an element from the right half is placed before remaining elements of the left half, all those remaining left elements form inversions with it, giving O(n log n) time.
Return the total number of inversion pairs as an integer.
Constraints
- 0 <= len(arr) <= 10^5
- -10^9 <= arr[i] <= 10^9
- Array elements may contain duplicates and negative numbers
- Equal elements (arr[i] == arr[j]) do NOT form an inversion
Examples
Input: [5, 7, 9, 2, 3, 12, 8, 4]
Expected Output: 13
Explanation: The 13 inversion pairs include (5,2),(5,3),(5,4),(7,2),(7,3),(7,4),(9,2),(9,3),(9,8),(9,4),(12,8),(12,4),(8,4).
Input: []
Expected Output: 0
Explanation: An empty array has no pairs, so 0 inversions.
Hints
- The naive solution is a double loop over all pairs (i, j) with i < j, counting when arr[i] > arr[j]. This is O(n^2) and a correct baseline.
- To get O(n log n), modify merge sort. The total inversion count equals inversions within the left half, plus inversions within the right half, plus cross-half inversions discovered during the merge.
- During the merge of two sorted halves, when you pick an element from the RIGHT half (because it is smaller than the current LEFT element), every remaining element in the left half is greater than it — add (number of remaining left elements) to the count.