Good morning! Here's our prompt for today.
This was submitted by user Hackleman.
Determine how "out of order" a list is by writing a function that returns the number of inversions in that list.
Two elements of a list L
, L[i]
and L[j]
, form an inversion if L[i] < L[j]
but i > j
.

For example, the list [5, 4, 3, 2, 1]
has 10
inversions since every element is out of order. They are the following: (5, 4), (5,3), (5,2), (5,1), (4,3), (4,2), (4,1), (3,2), (3,1), (2,1)
.
The list [2, 1, 4, 3, 5]
has two inversions: (2, 1)
and (4, 3)
.
Do this in better than O(N^2)
.
Constraints
- Length of the given array <=
100000
- Values in the array ranges from
-1000000000
to1000000000
- Expected time complexity :
O(nlogn)
- Expected space complexity :
O(1)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
26
def inversions(l):
# fill in
return l
​
​
import unittest
​
​
class Test(unittest.TestCase):
def test_1(self):
assert inversions([5, 4, 3, 2, 1]) == 10
print("PASSED: inversions for [5, 4, 3, 2, 1] should be 10")
​
def test_2(self):
assert inversions([2, 4, 1, 3, 5]) == 3
print("PASSED: inversions for [2, 4, 1, 3, 5] should be 3")
​
def test_3(self):
assert callable(inversion) == True
print("PASSED: `inversions` should be a function")
​
​
if __name__ == "__main__":
unittest.main(verbosity=2)
print("Nice job, 3/3 tests passed!")
​
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's how we would solve this problem...
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.