Thanks @areahints but I think the time complexity still remains the same irrespective of the list comprehension.

yes, I mentioned that my list comprehension didn't satisfy the complexity.

consider this solution;

def getInvCount(arr,n): return mergeGetInvCount(arr)[1] def mergeGetInvCount(arr): if len(arr) <= 1: return arr, 0 middle = int(len(arr) / 2) left, a = mergeGetInvCount(arr[:middle]) right, b = mergeGetInvCount(arr[middle:]) result, c = mergeGetSplitInvCount(left, right) return result, (a + b + c) def mergeGetSplitInvCount(left, right): result = [] count = 0 i,j = 0,0 left_len = len(left) while i < left_len and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) count += left_len - i j += 1 result += left[i:] result += right[j:] return result, count # Driver Code arr = [1, 20, 6, 4, 5] n = len(arr) print("Number of inversions are", getInvCount(arr,n))

Number of inversions are 5

that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?

We're a place where coders share, stay up-to-date and grow their careers.

We strive for transparency and don't collect excess data.

## re: Algorithm Question By Google VIEW POST

TOP OF THREAD FULL DISCUSSIONThanks @areahints but I think the time complexity still remains the same irrespective of the list comprehension.

yes, I mentioned that my list comprehension didn't satisfy the complexity.

consider this solution;

## Output

that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?