Mark As Completed Discussion

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.

Description

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 to 1000000000
  • 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?

PYTHON
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.

Returning members can login to stop seeing this.