Merge Sort: Counting Inversions Discussions |

2 years ago+ 0 comments

The reason why Python times out despite being O(n log n) is because of the pop(0) operation, which is actually O(n) time, which is nested within the merge() O(n) operation. Why is pop(0) O(n)?

The solution is to transform the list into a deque in O(n) time once, and then all pop(0) operations are now O(1).

from collections import deque
def countInversions(arr):
    # Write your code here
    global ans
    ans = 0
    
    def mergesort(x):
        n = len(x)
        if len(x) == 1:
            return x
        else:
            return merge(mergesort(x[:n//2]), mergesort(x[n//2:]))
    def merge(a, b):
        # print(a, b) 
        res = []
        a = deque(a)
        b = deque(b)
        while a and b:
            x = a[0]
            y = b[0]
            if y < x:
                global ans
                ans += len(a)
                res.append(y)
                b.popleft()
            else:
                res.append(x)
                a.popleft()
        if a:
            res.extend(a)
        if b:
            res.extend(b)
        return res
    mergesort(arr)
    return ans

Cookie support is required to access HackerRank