Algorithms for Coding Interviews in Python/

...

/

Solution: Inversion Count in a List

Solution: Inversion Count in a List

This lesson explains how to calculate inversion count in a divide and conquer paradigm.

We'll cover the following...

Solution: 1

The naive solution to this problem would be to:

  1. Pick an element from the list
  2. Compare it with all elements to its right
  3. If the element on the right is smaller, increment the inversion count
Python 3.5
def inversion_count(lst):
    """
    Function to find Inversion Count
    :param lst: List of integers
    :return: The inversion count of the list
    """
    size = len(lst)
    inv_count = 0  # variable to store inversion count
    
    for curr in range(size - 1): 
      for right in range(curr + 1, size): 
        if lst[curr] > lst[right]:
          inv_count += 1
    return inv_count 
# Driver code to test above functions
if __name__ == '__main__':
    lst = [3, 2, 8, 4]
    result = inversion_count(lst)
    print("Number of inversions are", result)

Time complexity

The list is traversed once for each element in it. It runs in O(n2)O(n^2), thus, it is inefficient.

...