Skip to content

Files

Latest commit

268e7b9 · Apr 18, 2020

History

History

problem044

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Apr 18, 2020
Apr 18, 2020
Apr 18, 2020

Daily Coding Problem: Problem #44

Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

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.