44_Google_Count_Inversions_In_Unsorted_List.py

"""

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.

"""

# idea: use merge sort to count the number of inversions:
#       Runtime of merge sort is O(n*log(n)) which is less than O(n^2)


def merge(list_a_with_inv_tuple, list_b_with_inv_tuple):
    merged_list = []

    list_a, invs_in_a = list_a_with_inv_tuple
    list_b, invs_in_b = list_b_with_inv_tuple

    len_a = len(list_a)
    len_b = len(list_b)

    inversions = invs_in_a + invs_in_b
    iter_a, iter_b = 0, 0
    while iter_a < len_a and iter_b < len_b:
        if list_a[iter_a] < list_b[iter_b]:
            merged_list.append(list_a[iter_a])
            iter_a += 1
        else:
            merged_list.append(list_b[iter_b])
            # the num "list_b[iter_b]" must be less than all the values list_a[iter_a:]
            inversions += len(list_a[iter_a:])
            iter_b += 1

    # append the remaining number to the list
    while iter_a < len_a:
        merged_list.append(list_a[iter_a])
        iter_a += 1

    while iter_b < len_b:
        merged_list.append(list_b[iter_b])
        iter_b += 1

    return merged_list, inversions


def merge_sort(list):
    # if list only contains one number than just return the list and 0 inversions
    if len(list) == 1:
        return list, 0

    # otherwise, divide list into two and run merge sort on tow smaller lists
    mid = len(list)//2
    return merge(merge_sort(list[:mid]), merge_sort(list[mid:]))


def count_inversions(list):
    _, inversions = merge_sort(list)
    return inversions


if __name__ == '__main__':
    assert count_inversions(list=[2, 4, 1, 3, 5]) ==3