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?
Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink.
Hide child comments as well
Confirm
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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;
Output
that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?