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.
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 complexity
I 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;
that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?