Good afternoon! 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
39
var assert = require('assert');
​
// Please enter your coding solution here.
function inversions(list) {
// fill in
// return # of inversions
return count;
}
// Though at AlgoDaily we have a strong bias towards Javascript,
// feel free to use any language you'd like!
​
try {
assert.equal(inversions([5, 4, 3, 2, 1]), 10);
​
console.log('PASSED: ' + 'inversions for [5, 4, 3, 2, 1] should be 10');
} catch (err) {
console.log(err);
}
​
try {
assert.equal(inversions([2, 4, 1, 3, 5]), 3);
​
console.log('PASSED: ' + 'inversions for [2, 4, 1, 3, 5] should be 3');
} catch (err) {
console.log(err);
}
​
try {
assertIsFunction(inversions, '`inversions` should be a function');
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
We'll now take you through what you need to know.
How do I use this guide?