Problem statement

https://binarysearch.com/problems/Bubble-Swap/

Solution 1

In fact what we need to found in this problem is number of inversions in A * B^{-1} permutation.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, A, B):
        n = len(A)
        d = {x: i for i, x in enumerate(A)}
        C = [d[B[i]] for i in range(n)]
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                if C[i] > C[j]: ans += 1
        return ans

Solution 2

In fact we can do it in O(n log n), using BIT or segment tree.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class BIT:
    def __init__(self, n):
        self.sums = [0] * (n+1)
    
    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] += delta
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

class Solution:
    def solve(self, A, B):
        n = len(A)
        d = {x: i for i, x in enumerate(A)}
        C = [d[B[i]] for i in range(n)]
        bit = BIT(n)
        ans = 0
        for i in range(n - 1, -1, -1):
            ans += bit.query(C[i] + 1)
            bit.update(C[i] + 1, 1)
        return ans