Given a permutation of first n natural numbers as an array and an integer k. Print the lexicographically largest permutation after at most k swaps.
Example 1:
Input:
n=5
k=3
arr[] = {4, 5, 2, 1, 3}
Output: 5 4 3 2 1
Explanation: Swap 1^{st} and 2^{nd} elements: 5 4 2 1 3 
             Swap 3^{rd} and 5^{th} elements: 5 4 3 1 2 
             Swap 4^{th} and 5^{th} elements: 5 4 3 2 1 
Example 2:
Input:
n=3
k=1
arr[] = {2, 1, 3}
Output: 3 1 2
Explanation: Swap 1^{st} and 3^{re} elements: 3 1 2 
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function KswapPermutation() that takes array arr, integer n and integer k as parameters and modifies the array arr and does not return anything.
 
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).
Constraints:
2 ≤ n ≤ 10^{6}
1 ≤ k ≤ n

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def KswapPermutation(self,arr,n,k):

        

Solutions:
class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {}
		arr1 = []
		c = 0
		for i in range(0, len(arr)):
			d[arr[i]] = i
		for i in range(len(arr), 0, -1):
			arr1.append(i)
		i = 0
		while i < len(arr) and c < k:
			if arr[i] == arr1[i]:
				i += 1
				continue
			else:
				ind = d[arr1[i]]
				temp = arr[i]
				arr[i] = arr[ind]
				arr[ind] = temp
				d[arr[i]] = i
				d[arr[ind]] = ind
				c += 1
				i += 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {}
		for i in range(0, n):
			d[arr[i]] = i
		t = n
		for i in range(0, n):
			if k == 0:
				break
			if arr[i] == t:
				t -= 1
				continue
			else:
				ind1 = i
				ind2 = d[t]
				ele = arr[i]
				(arr[i], arr[d[t]]) = (arr[d[t]], arr[i])
				d[t] = ind1
				d[ele] = ind2
				t -= 1
				k -= 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		dic = {}
		for i in range(n):
			if arr[i] != n - i:
				dic[arr[i]] = i
		for i in range(n):
			if arr[i] != n - i:
				j = dic[n - i]
				del dic[n - i]
				dic[arr[i]] = j
				(arr[i], arr[j]) = (arr[j], arr[i])
				k -= 1
			if k == 0:
				return arr
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		_max = n
		d = {num: i for (i, num) in enumerate(arr)}
		i = 0
		while k > 0 and i < n:
			j = d[_max]
			if i == j:
				pass
			else:
				(arr[i], arr[j]) = (arr[j], arr[i])
				(d[arr[i]], d[arr[j]]) = (d[arr[j]], d[arr[i]])
				k -= 1
			_max -= 1
			i += 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		arr2 = list(range(n, 0, -1))
		i = 0
		while k and i < n:
			if arr[i] != arr2[i]:
				k -= 1
				index = d[arr2[i]]
				d[arr[i]] = index
				arr[index] = arr[i]
				arr[i] = arr2[i]
			i += 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		h = {}
		for i in range(n):
			h[arr[i]] = i
		if n <= k:
			arr.sort()
			arr.reverse()
		else:
			for j in range(n, 0, -1):
				if k > 0:
					initial_index = h[j]
					best_index = n - j
					if initial_index != best_index:
						h[j] = best_index
						element = arr[best_index]
						h[element] = initial_index
						(arr[best_index], arr[initial_index]) = (arr[initial_index], arr[best_index])
						k -= 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		i = 0
		p = [0 for i in range(n + 1)]
		for i in range(n):
			p[arr[i]] = i
		i = 0
		for i in range(n):
			if arr[i] == n - i:
				continue
			if k == 0:
				break
			temp = arr[i]
			(arr[i], arr[p[n - i]]) = (arr[p[n - i]], arr[i])
			p[temp] = p[n - i]
			k -= 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		for i in range(n):
			if k == 0:
				return
			if arr[i] == n - i:
				continue
			largestpos = d[n - i]
			d[arr[i]] = largestpos
			d[n - i] = i
			(arr[i], arr[largestpos]) = (arr[largestpos], arr[i])
			k -= 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		i = 0
		m = len(arr)
		d = {x: i for (i, x) in enumerate(arr)}
		while k and i < len(arr):
			j = d[m]
			if i == j:
				pass
			else:
				k -= 1
				(arr[i], arr[j]) = (arr[j], arr[i])
				(d[arr[i]], d[arr[j]]) = (d[arr[j]], d[arr[i]])
			i += 1
			m -= 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		pos = {}
		for i in range(n):
			pos[arr[i]] = i
		for i in range(n):
			if k == 0:
				return
			if arr[i] == n - i:
				continue
			temp = pos[n - i]
			(pos[n - i], pos[arr[i]]) = (pos[arr[i]], pos[n - i])
			(arr[pos[n - i]], arr[temp]) = (arr[temp], arr[pos[n - i]])
			k -= 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		pos = {}
		n = len(arr)
		for index in range(n):
			pos[arr[index]] = index
		i = n
		while k > 0 and i > 0:
			if pos[i] == n - i:
				i = i - 1
				continue
			else:
				temp = pos[i]
				pos[arr[n - i]] = pos[i]
				pos[i] = n - i
				(arr[n - i], arr[temp]) = (arr[temp], arr[n - i])
				k = k - 1
			i = i - 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		mydict = {}
		for i in range(n):
			mydict[arr[i]] = i
		i = 0
		while i < n and k > 0:
			if arr[i] != n - i:
				arr[mydict[n - i]] = arr[i]
				mydict[arr[i]] = mydict[n - i]
				arr[i] = n - i
				k -= 1
			i += 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {}
		brr = arr.copy()
		brr = sorted(arr, reverse=True)
		if brr == arr:
			return arr
		for i in range(len(arr)):
			d[arr[i]] = i
		i = 0
		c = 0
		while i < len(arr) and c < k:
			if arr[i] < n - i:
				temp = d[n - i]
				(arr[i], arr[temp]) = (arr[temp], arr[i])
				d[arr[i]] = i
				d[arr[temp]] = temp
				c = c + 1
			i = i + 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {x: i for (i, x) in enumerate(arr)}
		maxi = n
		i = 0
		while k and i < n:
			j = d[maxi]
			if i == j:
				i += 1
				maxi -= 1
				continue
			(arr[i], arr[j]) = (arr[j], arr[i])
			(d[arr[i]], d[arr[j]]) = (d[arr[j]], d[arr[i]])
			k -= 1
			i += 1
			maxi -= 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		index = {}
		for i in range(n):
			index[arr[i]] = i
		swaps = i = 0
		while swaps < k and i < n:
			if arr[i] < n - i:
				idx = index[n - i]
				(arr[i], arr[idx]) = (arr[idx], arr[i])
				index[n - i] = i
				index[arr[idx]] = idx
				swaps += 1
			i += 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {arr[i]: i for i in range(n)}
		m = n
		for i in range(n):
			if arr[i] < m:
				temp = arr[i]
				arr[i] = m
				arr[d[m]] = temp
				(d[temp], d[m]) = (d[m], d[temp])
				k -= 1
			if k == 0:
				break
			m -= 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		hmap = {v: i for (i, v) in enumerate(arr)}
		i = 0
		cnts = 0
		while i < n:
			v = n - i
			if arr[i] != v:
				j = hmap[v]
				hmap[v] = i
				hmap[arr[i]] = j
				(arr[i], arr[j]) = (arr[j], arr[i])
				cnts += 1
				if cnts == k:
					break
			i += 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		arr2 = sorted(arr, reverse=True)
		hmap = {v: i for (i, v) in enumerate(arr)}
		i = 0
		cnts = 0
		while i < n:
			if arr[i] != arr2[i]:
				j = hmap[arr2[i]]
				hmap[arr[j]] = i
				hmap[arr[i]] = j
				(arr[i], arr[j]) = (arr[j], arr[i])
				cnts += 1
				if cnts == k:
					break
			i += 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {}
		for i in range(len(arr)):
			d[arr[i]] = i
		p = 0
		while k and n:
			if arr[p] == n:
				p += 1
				n -= 1
				continue
			temp = arr[p]
			(arr[p], arr[d[n]]) = (arr[d[n]], arr[p])
			(d[n], d[temp]) = (d[temp], d[n])
			k -= 1
			n -= 1
			p += 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		p = [-1 for i in range(n + 1)]
		for i in range(n):
			p[arr[i]] = i
		j = 0
		while j < n and k > 0:
			if arr[j] == n - j:
				j += 1
				continue
			arr[p[n - j]] = arr[j]
			p[arr[j]] = p[n - j]
			arr[j] = n - j
			p[n - j] = j
			k -= 1
			j += 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		indices = {}
		for i in range(n):
			indices.setdefault(arr[i], i)
		for i in range(n):
			if k == 0:
				break
			if arr[i] != n - i:
				ind2 = indices[n - i]
				indices[arr[i]] = indices[n - i]
				indices[n - i] = i
				(arr[i], arr[ind2]) = (arr[ind2], arr[i])
				k -= 1


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		x = n
		ind = 0
		while x:
			if d[x] != ind:
				val = arr[ind]
				(arr[d[x]], arr[ind]) = (arr[ind], arr[d[x]])
				d[val] = d[x]
				d[x] = ind
				k = k - 1
			if k == 0:
				break
			ind += 1
			x -= 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = dict.fromkeys(arr, 0)
		for i in range(n):
			d[arr[i]] = i
		b = sorted(arr, reverse=True)
		i = 0
		while i < n and k > 0:
			if arr[i] != b[i]:
				t = arr[i]
				(arr[i], arr[d[b[i]]]) = (b[i], arr[i])
				d[t] = d[b[i]]
				k -= 1
			i += 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = {}
		for i in range(len(arr)):
			d[arr[i]] = i
		j = 0
		count = 0
		maxx = -1
		for i in range(n):
			if arr[i] > maxx:
				maxx = arr[i]
		while count < k:
			if j == n - 1:
				break
			if maxx > arr[j]:
				temp = arr[j]
				arr[j] = maxx
				arr[d[maxx]] = temp
				temp2 = d[maxx]
				d[maxx] = j
				d[temp] = temp2
				maxx -= 1
				j += 1
				count += 1
			else:
				maxx -= 1
				j += 1
		return arr


class Solution:

	def KswapPermutation(self, arr, n, k):
		d = dict()
		v = []
		for i in range(n):
			v.append(arr[i])
			d[v[i]] = i
		v.sort(reverse=True)
		i = 0
		while i < n and k > 0:
			if arr[i] != v[i]:
				arr[d[v[i]]] = arr[i]
				d[arr[i]] = d[v[i]]
				arr[i] = v[i]
				d[v[i]] = i
				k -= 1
			i += 1
		return arr