Skip to content

Instantly share code, notes, and snippets.

@priyankvex
Created August 8, 2019 16:27
Show Gist options
  • Save priyankvex/d2c642ce8e0c61bb70da9c2547828cf2 to your computer and use it in GitHub Desktop.
Save priyankvex/d2c642ce8e0c61bb70da9c2547828cf2 to your computer and use it in GitHub Desktop.
Minimum swaps needs to sort the array
class Solution(object):
def solution(self, a):
seen = {}
cycles = []
for i, n in enumerate(a):
if n == i:
continue
else:
if seen.get(n) is None:
cycle = 1
cur = n
seen[cur] = True
while seen.get(a[cur]) is None:
cur = a[cur]
cycle += 1
seen[cur] = True
cycles.append(cycle)
return sum(cycles) - len(cycles)
if __name__ == "__main__":
A = [0, 1, 2, 5, 4, 3]
ans = Solution().solution(A)
print(ans)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment