Given an array of n distinct elements. Find the minimum number of swaps required to sort the array in strictly increasing order.
Example 1:
Input:
nums = {2, 8, 5, 4}
Output:
1
Explaination:
swap 8 with 4.
Example 2:
Input:
nums = {10, 19, 6, 3, 5}
Output:
2
Explaination:
swap 10 with 3 and swap 19 with 5.
Your Task:
You do not need to read input or print anything. Your task is to complete the function minSwaps() which takes the nums as input parameter and returns an integer denoting the minimum number of swaps required to sort the array. If the array is already sorted, return 0. 
Expected Time Complexity: O(nlogn)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ nums_{i} ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Graph algorithms

Data structures

Starter code: 

class Solution:
    
    #Function to find the minimum number of swaps required to sort the array.
	def minSwaps(self, nums):
		#Code here

Solutions:
from collections import OrderedDict

class Solution:

	def minSwaps(self, nums):
		dic = OrderedDict()
		for i in range(len(nums)):
			dic[nums[i]] = i
		sorted_dic = OrderedDict(sorted(dic.items()))
		swaps = 0
		for (i, v) in enumerate(sorted_dic.values()):
			if i != v:
				(nums[i], nums[v]) = (nums[v], nums[i])
				(sorted_dic[nums[i]], sorted_dic[nums[v]]) = (sorted_dic[nums[v]], sorted_dic[nums[i]])
				swaps += 1
		return swaps


class Solution:

	def minSwaps(self, nums):

		def swap(i, idx, l1):
			temp = l1[i]
			l1[i] = l1[idx]
			l1[idx] = temp
		l = []
		for i in range(len(nums)):
			l.append([nums[i], i])
		l1 = sorted(l, key=lambda x: x[0])
		c = 0
		i = 0
		while i < len(nums):
			p = l1[i]
			v = p[0]
			idx = p[1]
			if i != idx:
				c = c + 1
				swap(i, idx, l1)
				i = i - 1
			i = i + 1
		return c


class Solution:

	def minSwaps(self, nums):
		graph = []
		length = len(nums)
		for i in range(length):
			graph.append([nums[i], i])
		graph.sort(key=lambda x: x[0])
		visited = [0 for i in range(length)]
		swaps = 0
		for i in range(length):
			if visited[i] or graph[i][1] == i:
				continue
			cycle_size = 0
			j = i
			while not visited[j]:
				visited[j] = 1
				cycle_size += 1
				j = graph[j][1]
			swaps += cycle_size - 1
		return swaps


class Solution:

	def minSwaps(self, nums):
		list1 = [[v, i] for (i, v) in enumerate(nums)]
		list1.sort()
		i = 0
		count = 0
		while i < len(nums):
			j = list1[i][1]
			if i == j:
				i += 1
			else:
				(list1[i], list1[j]) = (list1[j], list1[i])
				count += 1
		return count


class Solution:

	def minSwaps(self, arr):
		n = len(arr)
		ans = 0
		temp = arr.copy()
		temp.sort()
		dic = {}
		for i in range(n):
			dic[arr[i]] = i
		init = 0
		for i in range(n):
			if arr[i] != temp[i]:
				ans += 1
				init = arr[i]
				(arr[i], arr[dic[temp[i]]]) = (arr[dic[temp[i]]], arr[i])
				dic[init] = dic[temp[i]]
				dic[temp[i]] = i
		return ans


class Solution:

	def minSwaps(self, nums):
		numIndx = [[nums[i], i] for i in range(len(nums))]
		numIndx.sort()
		i = 0
		count = 0
		while i < len(nums):
			j = numIndx[i][1]
			if j == i:
				i += 1
			else:
				(numIndx[i], numIndx[j]) = (numIndx[j], numIndx[i])
				count += 1
		return count


class Solution:

	def minSwaps(self, arr):
		n = len(arr)
		arrpos = [*enumerate(arr)]
		arrpos.sort(key=lambda it: it[1])
		vis = {k: False for k in range(n)}
		ans = 0
		for i in range(n):
			if vis[i] or arrpos[i][0] == i:
				continue
			cycle_size = 0
			j = i
			while not vis[j]:
				vis[j] = 1
				j = arrpos[j][0]
				cycle_size += 1
			if cycle_size > 0:
				ans += cycle_size - 1
		return ans


class Solution:

	def minSwaps(self, nums):
		d = dict()
		for (k, v) in enumerate(nums):
			d[v] = k
		sorted_arr = sorted(nums)
		count = 0
		for i in range(len(nums)):
			if nums[i] != sorted_arr[i]:
				count += 1
				idx = d[sorted_arr[i]]
				(nums[i], nums[idx]) = (nums[idx], nums[i])
				d[nums[idx]] = idx
				d[nums[i]] = i
		return count


class Solution:

	def minSwaps(self, nums):
		ans = 0
		temp = nums.copy()
		temp.sort()
		h = {}
		n = len(nums)
		for i in range(n):
			h[nums[i]] = i
		init = 0
		for i in range(n):
			if nums[i] != temp[i]:
				ans += 1
				init = nums[i]
				(nums[i], nums[h[temp[i]]]) = (nums[h[temp[i]]], nums[i])
				h[init] = h[temp[i]]
				h[temp[i]] = i
		return ans


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		s = sorted(nums)
		index_dict = {nums[i]: i for i in range(n)}
		c = 0
		for i in range(n):
			if nums[i] != s[i]:
				c += 1
				j = index_dict[s[i]]
				(nums[i], nums[j]) = (nums[j], nums[i])
				(index_dict[nums[i]], index_dict[nums[j]]) = (i, j)
		return c


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		cur = []
		for i in range(n):
			cur.append([nums[i], i])
		cur.sort()
		vis = [False for i in range(n)]
		ans = 0
		for i in range(n):
			if vis[i] or cur[i][1] == i:
				continue
			else:
				cycle_size = 0
				j = i
				while vis[j] == False:
					vis[j] = True
					j = cur[j][1]
					cycle_size = cycle_size + 1
				ans = ans + max(0, cycle_size - 1)
		return ans


class Solution:

	def minSwaps(self, nums):
		d = {}
		for i in range(len(nums)):
			d[nums[i]] = i
		a = sorted(nums)
		visited = [False] * len(nums)
		c = ans = 0
		for i in range(len(nums)):
			c = 0
			j = i
			while not visited[j]:
				visited[j] = True
				j = d[a[j]]
				c += 1
			if c > 0:
				ans += c - 1
		return ans


class Solution:

	def minSwaps(self, nums):
		new_sort = sorted(nums)
		map = {}
		for (index, i) in enumerate(new_sort):
			map[i] = index
		answer = 0
		for (i, item) in enumerate(nums):
			while i != map[item]:
				temp = nums[map[item]]
				nums[map[item]] = item
				nums[i] = temp
				item = temp
				answer += 1
		return answer


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		h = [[nums[i], i] for i in range(n)]
		h.sort()
		(i, swaps) = (0, 0)
		while i < n:
			if h[i][1] != i:
				swaps += 1
				ind = h[i][1]
				(h[i], h[ind]) = (h[ind], h[i])
			else:
				i += 1
		return swaps


import copy
import math

class Solution:

	def minSwaps(self, nums):
		numIndx = [[nums[i], i] for i in range(len(nums))]
		numIndx.sort()
		i = 0
		count = 0
		while i < len(nums):
			j = numIndx[i][1]
			if j == i:
				i += 1
				continue
			(numIndx[i], numIndx[j]) = (numIndx[j], numIndx[i])
			count += 1
		return count


class Solution:

	def minSwaps(self, nums):
		arr = [[nums[i], i] for i in range(len(nums))]
		arr.sort()
		i = 0
		count = 0
		while i < len(nums):
			j = arr[i][1]
			if j == i:
				i += 1
				continue
			(arr[i], arr[j]) = (arr[j], arr[i])
			count += 1
		return count


class Solution:

	def minSwaps(self, nums):
		orig_map = {j: i for (i, j) in enumerate(nums)}
		sorted_arr = sorted(nums)
		res = 0
		for i in range(len(nums)):
			if nums[i] != sorted_arr[i]:
				res += 1
				curr = nums[i]
				(nums[i], nums[orig_map[sorted_arr[i]]]) = (nums[orig_map[sorted_arr[i]]], nums[i])
				(orig_map[curr], orig_map[sorted_arr[i]]) = (orig_map[sorted_arr[i]], orig_map[curr])
		return res


from collections import OrderedDict

class Solution:

	def minSwaps(self, nums):
		numIndx = [[nums[i], i] for i in range(len(nums))]
		numIndx.sort()
		i = 0
		count = 0
		while i < len(nums):
			j = numIndx[i][1]
			if j == i:
				i += 1
				continue
			(numIndx[i], numIndx[j]) = (numIndx[j], numIndx[i])
			count += 1
		return count


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		ss = sorted(range(n), key=lambda x: nums[x])
		r = 0
		for i in range(n):
			if ss[i] == i:
				continue
			rr = 0
			while ss[i] != i:
				k = ss[i]
				(ss[i], ss[k]) = (ss[k], k)
				rr += 1
			r += rr
		return r


class Solution:

	def minSwaps(self, a):
		k = [[a[i], i] for i in range(len(a))]
		k.sort()
		c = 0
		i = 0
		while i < len(a):
			if i == k[i][1]:
				i += 1
			else:
				c += 1
				x = k[i][1]
				temp = [0, 0]
				temp[0] = k[i][0]
				temp[1] = k[i][1]
				k[i][0] = k[x][0]
				k[i][1] = k[x][1]
				k[x][0] = temp[0]
				k[x][1] = temp[1]
		return c


class Solution:

	def minSwaps(self, nums):
		swapcount = 0
		d = {}
		for i in range(len(nums)):
			d[nums[i]] = i
		keys = list(nums)
		keys.sort()
		i = 0
		while i < len(nums):
			if d[keys[i]] == i:
				i += 1
			else:
				t = keys[i]
				keys[i] = keys[d[keys[i]]]
				keys[d[t]] = t
				swapcount += 1
		return swapcount


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		arr_copy = list(nums)
		arr_copy.sort()
		pos_dict = {arr_copy[i]: i for i in range(n)}
		swaps = 0
		visited = [False] * n
		for i in range(n):
			if visited[i] or nums[i] == arr_copy[i]:
				continue
			cycle_size = 0
			j = i
			while not visited[j]:
				visited[j] = True
				cycle_size += 1
				j = pos_dict[nums[j]]
			swaps += cycle_size - 1
		return swaps


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		v = [(nums[i], i) for i in range(n)]
		v.sort()
		count = 0
		i = 0
		while i < n:
			if i == v[i][1]:
				i += 1
			else:
				count += 1
				(v[v[i][1]], v[i]) = (v[i], v[v[i][1]])
		return count


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		temp = nums.copy()
		index_map = {}
		for i in range(n):
			index_map[nums[i]] = i
		nums.sort()
		swaps = 0
		for i in range(n):
			if nums[i] != temp[i]:
				swaps += 1
				val = temp[i]
				(temp[i], temp[index_map[nums[i]]]) = (temp[index_map[nums[i]]], temp[i])
				(index_map[nums[i]], index_map[val]) = (index_map[val], index_map[nums[i]])
		return swaps


class Solution:

	def minSwaps(self, nums):
		_ans = 0
		nums2 = nums.copy()
		nums2.sort()
		_map = {}
		N = len(nums2)
		for i in range(N):
			_map[nums[i]] = i
		for i in range(N):
			v1 = nums[i]
			v2 = nums2[i]
			if v1 == v2:
				continue
			else:
				index = _map[v2]
				(nums[i], nums[index]) = (nums[index], nums[i])
				_map[v1] = index
				_ans += 1
		return _ans


class Solution:

	def minSwaps(self, nums):
		li = []
		n = len(nums)
		for i in range(n):
			li.append((nums[i], i))
		li.sort()
		count = 0
		i = 0
		while i < n:
			if li[i][1] != i:
				count += 1
				temp = li[i][1]
				(li[i], li[temp]) = (li[temp], li[i])
				i -= 1
			i += 1
		return count


class Solution:

	def minSwaps(self, nums):
		v = []
		for i in range(len(nums)):
			v.append((nums[i], i))
		v = sorted(v)
		vis = [False for i in range(len(nums))]
		cnt = 0
		for i in range(len(v)):
			if vis[i] or v[i][1] == i:
				continue
			else:
				c = 0
				j = i
				while vis[j] == False:
					vis[j] = True
					j = v[j][1]
					c += 1
				cnt += c - 1
		return cnt


class Solution:

	def minSwaps(self, nums):
		index_nums = []
		res = 0
		for (c, i) in enumerate(nums):
			index_nums.append([i, c])
		index_nums.sort(key=lambda x: x[0])
		i = 0
		while i < len(nums):
			if i == index_nums[i][1]:
				pass
			else:
				index = index_nums[i][1]
				(index_nums[i], index_nums[index]) = (index_nums[index], index_nums[i])
				res += 1
				i -= 1
			i += 1
		return res


class Solution:

	def minSwaps(self, nums):
		lst = [[nums[i], i] for i in range(len(nums))]
		lst.sort()
		i = 0
		cnt = 0
		while i < len(nums):
			j = lst[i][1]
			if j == i:
				i += 1
				continue
			(lst[i], lst[j]) = (lst[j], lst[i])
			cnt += 1
		return cnt


class Solution:

	def minSwaps(self, arr):
		new = arr.copy()
		new.sort()
		dic = {}
		count = 0
		for i in range(n):
			dic[new[i]] = i
		for i in range(n):
			while i != dic[arr[i]]:
				temp = dic[arr[i]]
				(arr[i], arr[temp]) = (arr[temp], arr[i])
				count += 1
		return count


class Solution:

	def minSwaps(self, nums):
		idx = sorted(enumerate(nums), key=lambda x: x[1])
		(i, ans) = (0, 0)
		while i < len(nums):
			j = idx[i][0]
			if i == j:
				i += 1
			else:
				(idx[i], idx[j]) = (idx[j], idx[i])
				ans += 1
		return ans


class Solution:

	def minSwaps(self, nums):
		s = sorted(nums)
		ans = 0
		dic = {}
		for i in range(len(nums)):
			dic[s[i]] = i
		i = 0
		while i < len(nums):
			ind = dic[nums[i]]
			if i == ind:
				i += 1
			else:
				ans += 1
				(nums[i], nums[ind]) = (nums[ind], nums[i])
		return ans


import math

class Solution:

	def minSwaps(self, arr):
		sarr = arr[:]
		sarr.sort()
		act_pos = {}
		for i in range(n):
			ele = sarr[i]
			act_pos[ele] = i
		count = 0
		for i in range(n):
			while i != act_pos[arr[i]]:
				ele = arr[i]
				(arr[i], arr[act_pos[ele]]) = (arr[act_pos[ele]], arr[i])
				count += 1
		return count


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		arr_pos = [*enumerate(nums)]
		arr_pos.sort(key=lambda x: x[1])
		visited = {k: False for k in range(n)}
		ans = 0
		for i in range(n):
			if visited[i] or arr_pos[i][0] == i:
				continue
			cycle_size = 0
			j = i
			while not visited[j]:
				visited[j] = True
				j = arr_pos[j][0]
				cycle_size += 1
			if cycle_size > 0:
				ans += cycle_size - 1
		return ans


class Solution:

	def sortsecond(self, val):
		return val[0]

	def minSwaps(self, nums):
		l = []
		n = len(nums)
		for i in range(n):
			l.append([nums[i], i])
		l.sort()
		c = 0
		i = 0
		while i < n:
			if l[i][1] == i:
				i += 1
				continue
			else:
				c += 1
				temp = l[i][1]
				(l[i], l[temp]) = (l[temp], l[i])
				i -= 1
			i += 1
		return c


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		cur = [(nums[i], i) for i in range(n)]
		cur.sort()
		visited = [False] * n
		ans = 0
		for i in range(n):
			if visited[i] or cur[i][1] == i:
				continue
			size = 0
			j = i
			while not visited[j]:
				visited[j] = True
				j = cur[j][1]
				size += 1
			ans += size - 1 if size > 1 else 0
		return ans


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		visited = [False] * n
		pairs = []
		for i in range(n):
			pairs.append((nums[i], i))
		pairs.sort()
		count = 0
		for i in range(n):
			if visited[i] or pairs[i][1] == i:
				continue
			cycle_size = 0
			j = i
			while not visited[j]:
				visited[j] = True
				cycle_size += 1
				j = pairs[j][1]
			count += cycle_size - 1
		return count


class Solution:

	def swap(self, nums, i, j):
		(nums[i], nums[j]) = (nums[j], nums[i])
		return

	def minSwaps(self, nums):
		pairs = {}
		count = 0
		size = len(nums)
		for i in range(size):
			pairs[nums[i]] = i
		nums.sort()
		i = 0
		while i < size:
			if pairs.get(nums[i]) == i:
				i += 1
			else:
				self.swap(nums, i, pairs.get(nums[i]))
				count += 1
		return count


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		s = sorted(nums)
		ind = {}
		for i in range(n):
			ind[s[i]] = i
		count = 0
		for i in range(n):
			ii = i
			while nums[ind[nums[ii]]] != nums[ii]:
				jj = ind[nums[ii]]
				(nums[jj], nums[ii]) = (nums[ii], nums[jj])
				count += 1
		return count


class Solution:

	def minSwaps(self, nums):
		ans = 0
		store = dict()
		sortedArray = sorted(nums)
		for (i, items) in enumerate(nums):
			store[items] = i
		for i in range(len(nums)):
			if nums[i] != sortedArray[i]:
				ans += 1
				store[nums[i]] = store[sortedArray[i]]
				nums[store[sortedArray[i]]] = nums[i]
		return ans


class Solution:

	def __init__(self):
		self.count = 0

	def partition(self, arr, low, high):
		pivot = arr[high]
		pindex = low
		for i in range(low, high):
			if arr[i] < pivot:
				(arr[i], arr[pindex]) = (arr[pindex], arr[i])
				pindex += 1
		(arr[high], arr[pindex]) = (arr[pindex], arr[high])
		self.count += 1
		return pindex

	def quickSort(self, arr, low, high):
		if low < high:
			p = self.partition(arr, low, high)
			self.quickSort(arr, low, p - 1)
			self.quickSort(arr, p + 1, high)

	def minSwaps(self, nums):
		n = len(nums)
		arrpos = [*enumerate(nums)]
		arrpos.sort(key=lambda it: it[1])
		vis = {k: False for k in range(n)}
		ans = 0
		for i in range(n):
			if vis[i] or arrpos[i][0] == i:
				continue
			cycle_size = 0
			j = i
			while not vis[j]:
				vis[j] = True
				j = arrpos[j][0]
				cycle_size += 1
			if cycle_size > 0:
				ans += cycle_size - 1
		return ans


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		v = nums.copy()
		m = {}
		for i in range(n):
			m[nums[i]] = i
		v.sort()
		c = 0
		for i in range(n):
			if v[i] != nums[i]:
				in_ = m[v[i]]
				(nums[i], nums[in_]) = (nums[in_], nums[i])
				(m[nums[i]], m[nums[in_]]) = (m[nums[in_]], m[nums[i]])
				c += 1
		return c


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		ordered_nums = sorted(nums)
		go_to = list()
		for i in range(n):
			x = nums[i]
			idx = self.binarySearch(0, n - 1, x, ordered_nums)
			go_to.append(idx)
		visited = [False] * n
		ans = 0
		for i in range(n):
			if visited[i] == False:
				count = 0
				j = i
				while visited[j] == False:
					visited[j] = True
					count += 1
					j = go_to[j]
				ans += count - 1
		return ans

	def binarySearch(self, start, end, x, nums):
		while start <= end:
			mid = (start + end) // 2
			if nums[mid] <= x:
				start = mid + 1
			else:
				end = mid - 1
		return start - 1


class Solution:

	def minSwaps(self, M):
		v = []
		for i in range(n):
			v.append([M[i], i])
		v.sort()
		swaps = 0
		i = 0
		while i < n:
			if i == v[i][1]:
				i += 1
				continue
			x = v[i][1]
			(v[i], v[x]) = (v[x], v[i])
			swaps += 1
		return swaps


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		ans = 0
		tmpArr = []
		for i in range(len(nums)):
			tmpArr.append([nums[i], i])
		tmpArr.sort()
		visited = [False for _ in range(n)]
		for i in range(n):
			if visited[i] or tmpArr[i][1] == i:
				continue
			j = i
			cycleCnt = 0
			while not visited[j]:
				visited[j] = True
				cycleCnt += 1
				j = tmpArr[j][1]
			ans += cycleCnt - 1
		return ans
		nums.sort()


class Solution:

	def minSwaps(self, nums):
		N = len(nums)
		visited = [False for i in range(N)]
		check = []
		for i in range(N):
			check.append([nums[i], i])
		check.sort(key=lambda x: x[0])
		for i in range(N):
			if nums[i] == check[i][0]:
				visited[i] = True
		total = 0
		for i in range(N):
			if visited[i] == False:
				visited[i] = True
				index = check[i][1]
				count = 0
				while True:
					if index == i:
						break
					visited[index] = True
					index = check[index][1]
					count += 1
				total += count
		return total


class Solution:

	def minSwaps(self, nums):
		arr = []
		n = len(nums)
		for i in range(n):
			arr.append([nums[i], i])
		arr.sort()
		brr = [0 for i in range(n)]
		visited = [False for i in range(n)]
		for i in range(n):
			brr[arr[i][1]] = i
		ans = 0
		for i in range(n):
			if visited[i] == False:
				clen = 0
				idx = i
				while visited[idx] == False:
					clen += 1
					visited[idx] = True
					idx = brr[idx]
				ans += clen - 1
		return ans


class Solution:

	def minSwaps(self, nums):
		positions = {}
		nums_sorted = sorted(nums)
		for i in range(len(nums)):
			positions[nums[i]] = i
		n_swaps = 0
		for i in range(len(nums)):
			ev = nums_sorted[i]
			av = nums[i]
			if ev != av:
				n_swaps += 1
				ev_currently_at = positions[ev]
				av_currently_at = i
				(nums[ev_currently_at], nums[av_currently_at]) = (nums[av_currently_at], nums[ev_currently_at])
				positions[av] = ev_currently_at
				positions[ev] = i
		return n_swaps


class Solution:

	def minSwaps(self, arr):
		aux = [*enumerate(arr)]
		aux.sort(key=lambda it: it[1])
		vec = [None] * len(arr)
		for (idx, ele) in enumerate(aux):
			vec[ele[0]] = idx
		visited = [False] * len(arr)
		swaps = 0
		for i in range(n):
			visited[i] = True
			nextele = vec[i]
			while visited[nextele] is not True:
				swaps += 1
				visited[nextele] = True
				i = nextele
				nextele = vec[i]
		return swaps


class Solution:

	def minSwaps(self, nums):
		n = len(nums)
		visited = [False] * n
		nodes = list(enumerate(nums))
		nodes.sort(key=lambda x: x[1])
		swaps = 0
		for i in range(n):
			if visited[i] or nodes[i][0] == i:
				continue
			cycle_size = 0
			j = i
			while not visited[j]:
				visited[j] = True
				j = nodes[j][0]
				cycle_size += 1
			swaps += cycle_size - 1
		return swaps


class Solution:

	def minSwaps(self, nums):
		hashmap = dict()
		for (k, v) in enumerate(nums):
			hashmap[v] = k
		temp = sorted(nums)
		count = 0
		for (k, v) in enumerate(temp):
			if nums[k] != v:
				nums[hashmap[v]] = nums[k]
				hashmap[nums[k]] = hashmap[temp[k]]
				nums[k] = v
				hashmap[v] = k
				count += 1
		return count


class Solution:

	def minSwaps(self, nums):
		c = 0
		n = len(nums)
		lis = [[nums[i], i] for i in range(n)]
		lis.sort()
		j = 0
		c = 0
		while j < n:
			k = lis[j][1]
			if k == j:
				j += 1
				continue
			(lis[j], lis[k]) = (lis[k], lis[j])
			c += 1
		return c


class Solution:

	def minSwaps(self, nums):
		mp = {}
		cnt = 0
		temp = sorted(nums)
		n = len(nums)
		for i in range(n):
			mp[nums[i]] = i
		for i in range(n):
			if nums[i] != temp[i]:
				cnt += 1
				val = nums[i]
				(nums[i], nums[mp[temp[i]]]) = (nums[mp[temp[i]]], nums[i])
				mp[val] = mp[temp[i]]
				mp[temp[i]] = i
		return cnt


class Solution:

	def f(self, nums, arrS, indx, count, adj):
		while arrS[indx] != nums[indx]:
			(nums[indx], nums[adj[arrS[indx]]]) = (nums[adj[arrS[indx]]], nums[indx])
			(adj[arrS[indx]], adj[nums[indx]]) = (adj[nums[indx]], adj[arrS[indx]])
			indx = adj[nums[indx]]
			count[0] += 1

	def minSwaps(self, nums):
		count = [0]
		arrS = sorted(nums)
		n = len(nums)
		adj = {}
		for i in range(n):
			adj[nums[i]] = i
		for i in range(n):
			if nums[i] != arrS[i]:
				self.f(nums, arrS, i, count, adj)
		return count[0]


class Solution:

	def minSwaps(self, arr):
		n = len(arr)
		temp = []
		for i in range(0, n):
			temp.append((arr[i], i))
		temp.sort()
		swaps = 0
		for i in range(0, n):
			while temp[i][0] != arr[i]:
				idx = temp[i][1]
				(temp[i], temp[idx]) = (temp[idx], temp[i])
				swaps += 1
		return swaps


class Solution:

	def minSwaps(self, nums):
		L = len(nums)
		A = []
		for i in range(L):
			A.append([nums[i], i])
		A.sort()
		i = 0
		Ans = 0
		while i < L:
			if i == A[i][1]:
				i += 1
				continue
			else:
				(A[A[i][1]], A[i]) = (A[i], A[A[i][1]])
				Ans += 1
				continue
		return Ans