Hackerrank - Largest Permutation Solution
1 min read

Hackerrank - Largest Permutation Solution

Hackerrank - Largest Permutation Solution

You are given an unordered array of unique integers incrementing from . You can swap any two elements a limited number of times. Determine the largest lexicographical value array that can be created by executing no more than the limited number of swaps.

For example, if  and the maximum swaps , the following arrays can be formed by swapping the  with the other elements:[2,1,3,4][3,2,1,4][4,2,3,1]

The highest value of the four (including the original) is . If , we can swap to the highest possible value: .

Function Description

Complete the largestPermutation function in the editor below. It must return an array that represents the highest value permutation that can be formed.

largestPermutation has the following parameter(s):

  • k: an integer that represents the limit of swaps
  • arr: an array of integers

Input Format

The first line contains two space-separated integers  and , the length of  and the maximum swaps that can be performed. The second line contains  unique space-separated integers  where .

Constraints


Output Format

Print the lexicographically largest permutation you can make with at most  swaps.
Sample Input 0

5 1
4 2 3 5 1

Sample Output 0

5 2 3 4 1

Explanation 0

You can swap any two numbers in  and see the largest permutation is

Sample Input 1

3 1
2 1 3

Sample Output 1

3 1 2

Explanation 1

With 1 swap we can get ,  and . Of these,  is the largest permutation.

Sample Input 2

2 1
2 1

Sample Output 2

2 1

Explanation 2

We can see that  is already the largest permutation. We don't make any swaps.

Solution in Python

def largestPermutation(k, arr):
    a = dict(enumerate(arr))
    b = {v:k for k,v in a.items()}
    l = len(arr)
    for i in range(l):
        if k and a[i]!=l-i:
            x = a[i]
            y = b[l-i]
            a[i] = l-i
            a[y] = x
            b[x] = y
            k-=1
        yield a[i]
n,k = map(int,input().split())
arr = list(map(int,input().split()))
print(*largestPermutation(k, arr))

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×