QUESTION
We can determine how "out of order" an array A is by counting the number of inversions it has.
Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j.
That is, a smaller element appears after a larger element.
CHALLENGE
Given an array, count the number of inversions it has. Do this faster than O(N^2) time.
You may assume each element in the array is distinct.
For example, a sorted list has zero inversions.
The array [2, 4, 1, 3, 5] has three inversions: (2, 1), (4, 1), and (4, 3).
The array [5, 4, 3, 2, 1] has ten inversions: every distinct pair forms an inversion.
Top comments (3)
Hi @theghostyced . so I decided to try and solve this on my own and I want to share my insights
my first solution was to
write some logicgoogle the question and I came across a solution that didn't satisfy the complexityI then tried to rewrite this using list comprehension, you can see my effort here
but this also revealed the answers which you can use to solve this question.
Thanks @areahints but I think the time complexity still remains the same irrespective of the list comprehension.
yes, I mentioned that my list comprehension didn't satisfy the complexity.
consider this solution;
Output
that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?