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

Access this course and 1400+ top-rated courses and projects.