Problem statement

https://binarysearch.com/problems/Number-of-Swaps-to-Sort/

Solution

What we need to do is given permutation for each cycle in this permutation we need len(cycle) - 1 swaps to fix it. Here I reuse my function perm_loops, which return loop representation of permutation.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        def perm_loops(x, n):
            V, ans = set(), []
            for i in range(n):
                if i in V: continue
                q = i
                ans += [[q]]
                V.add(i)
                while x[q] != i:
                    ans[-1] += [x[q]]
                    q = x[q]
                    V.add(q)
            return ans

        n = len(nums)
        d = {x:i for i, x in enumerate(sorted(nums))}
        perm = [d[x] for x in nums]
        out = perm_loops(perm, n)
        return sum(len(x) - 1 for x in out)