# Largest Permutation | InterviewBit | Solution Explained

I explain the solution to Largest Permutation on InterviewBit using visuals in simple words.

**Contents**hide

## 0. Largest Permutation: Problem Discussion

### 0.0. IO Format

- input:
- Array A of a random permutation of number from 1 to N (both inclusive)
- Integer B, the number of swaps we can make in A (pick any 2 indices and swap them)

- output:
- return the largest permutation of numbers possible

- constraints:
- 1 <= N <= 1e6
- 1 <= B <= 1e9

### 0.1. Examples

## 1. Largest Permutation: Observations & Logic

### 1.0. Intuitions

Let’s take the case two examples to understand this better.

In the first test case, we have [1,2,3,4] array and the number of swaps we can make is 1. This means we have to find a number which has the most bang for its buck. That is, since we can only make one swap, we have to find a number that can increase the value of the permutation by a lot.

The number is thus 4, which we can swap out with 1. This gives us [4,2,3,1]. Note how only 1 and 4 exchange positions and 2 and 3 remain as is.

The idea of *finding the element with the most bang for the buck* seems important.

### 1.1. The most bang for your buck (mbfyb)

Well, what if we now consider the second case: A = [3,2,4,1,5] and B = 3?

In this, we go through multiple iterations. In the first iteration, we proceed as earlier. We see that 5 is in the last position and we can make the answer better if we shift 5 to its best possible position – the first place, since there is no other number that can come at the 0th index and make this answer better.

Now we have [3,2,4,1,5] –> [5,2,4,1,3].

Note: Although shifting 3 to the last place, right from the first might look like a bad idea, we don’t really have a lot of choice – at this point, shifting 5 to its best possible position (0th) is the best and we can worry about 3 later.

Now this consumes 1 B, but we still have 2 left. That is, we can make 2 more swaps. What then about the second iteration?

We take [5,2,4,1,3] and we find the remaining number which has the mbfyb. 5 is already in its position, but perhaps we can try out 4?

Doing that we get [5,4,2,1,3] (swapping 2 and 4).

Then, in the final iteration (only 1 B remains now), we can swap 2 and 3, since 3 is the only element after 5 and 4 which has the mbfyb.

If you notice, all we have done up till now is to ensure that we are looking out for the element N then N-1 and then N-2 and so on. That is, we are greedily replacing the higher elements.

### 1.2. Implementation level detail

One quick note: What do we do if a number is present in its appropriate index? For example, what if we have [5,2,3,4,1] and B = 1?

In this case, we already have N = 5, the biggest element in the 0th position – the best position it could be in. But we still have B = 1, that is, one swap we can make. So, we can swap 4 to the 1st index, swapping out 2.

Thus, the array will look like: [5,4,3,2,1]. Oh and if B were >= 1, the answer won’t change. Think why 😉

Another detail to mention is that we need to keep a track of where each element is. That is, we need to know that 4 is at the index 4. So, then we can ask the element at index 1 (element = 2) to exchange positions. To keep a track, we can use a dictoinary.

*There is a sweet little space optimization we can do, and not use the dictionary/hashmap at all.*

## 2. Largest Permutation: Optimized Implementation

### 2.0. Code

class Solution: # @param A : list of integers # @param B : integer # @return a list of integers def solve(self, A, B): i = 0 _max = len(A) d = {x: i for i, x in enumerate(A)} while B and i < len(A): j = d[_max] if i == j: pass else: B -= 1 A[i], A[j] = A[j], A[i] d[A[i]], d[A[j]] = d[A[j]], d[A[i]] i += 1 _max -= 1 return A

### 2.1. Complexity Analysis

- Time:
`O(N)`

, for iterating through N elements in the array (even if B is large, the iterator i will make the program terminate in`O(N)`

time) - Space:
`O(N)`

, for storing the dictionary

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

Please write the proof.

This solution need an amendment for 2 digit number.