#4 Largest Permutation:

date posted: 2020-05-05

TMI of the day

1. My neck is hurting, some kind of muscle pain. Okay this was hardcore tmi sorry.

Solutions

Again, greedy approach will be taken to solve this problem. There are two ways of doing it.

1. Get all possible array and take most optimal
2. Have base array, update it each time more optimal array arise so in the end your base array would be most optimal.

#1 Try

• Only trying for k = 1
• given an array, I find highest number in an array and swap it with the first element. Since having largest value as first element will give highest possible lexicographical value when k = 1.

def largestPermutation(k, arr):
    for i_swap in range(k):
        high_pos = arr.index(max(arr))
        arr[0], arr[high_pos] = arr[high_pos], arr[0] 
    return arr

• This passes all test case but it won't work for k > 1
• As k increase we must increase position to swap accordingly. ex:when k = 2 first find largest value and swap it with first element then find largest from elements ignoring the first and swap it with second element.

#2 Try

• As we loop thorugh high_pos, arr[i:] therefore ignoring already swapped value
• find position of higest value from arr[i:] swap it with ith position. Note that previous values in array are swapped already.

def largestPermutation(k, arr):
    for i in range(k):
        high_pos = arr.index(max(arr[i:]))
        arr[i], arr[high_pos] = arr[high_pos], arr[i] 
    return arr

ex: if I pass in k = 2 , arr = [1,1,1,2,2,2]

• first loop it correctly swaps giving me [2,1,1,1,2,2].
• second loop I am looking for max value in [1,1,1,2,2] which should give an index value of 3 again. It gives high_pos = 0 instead. Giving arr = [1,2,1,1,2,2]

#3 Try

• Add i at the end because we will swap values in original arr[:] thus must add value that has been cut off.
• If k > len(arr) it outputted error because arr[k:] wouldn't exist if k > len(arr), so replaced k with len(arr) if k was larger.

def largestPermutation(k, arr):
    if k <= len(arr):
        num_swaps = k
    else:
        num_swaps = len(arr)
    for i in range(num_swaps):
        high_pos = arr[i:].index(max(arr[i:])) + i
        arr[i], arr[high_pos] = arr[high_pos], arr[i] 
    return arr

• Passes more test case but still fails on 7 of them.

#4 Other's Solution

• First, I want to say you must read questions carefully. I've been trying to figure out solution to this problem however I've misread the question therefore was trying to understand one line that seemed wrong to me.

def KswapPermutation(arr, n, k): 
    pos = {} 
    for i in range(n): 
        pos[arr[i]] = i 
  
    for i in range(n): 
        if k == 0: 
            break

        if (arr[i] == n-i): 
            continue
        temp = pos[n-i] 

        pos[arr[i]] = pos[n-i] 
        pos[n-i] = i 
  
        arr[temp], arr[i] = arr[i], arr[temp] 

        k = k-1

let arr = [4,5,2,1,3], k = 3

1. Given an array create a dictionary where key represents a number and value represents its index. We would get pos = {4:0, 5:1, 2:2, 1:3, 3:4}
2. Onto second for loop, our k = 3 therefore we go onto next if statement.
3. Note since array's largest value would equal to its length since array consists of integers incrementing from 1 this line checks if largest value is already in the right position.
4. temp holds largest value since in dictionary its value will change
5. If not already in the right position we change our dictionary so pos = {4:1, 5:0, 2:2, 1:3, 3:4}
6. Swap current position with largest value.
7. decrease k by 1.