# Largest Permutation | InterviewBit | Solution Explained

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

## 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

## 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

##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

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

June 13, 2022

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

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

1. Srishti Chopra :July 23, 2022 at 11:29 am

2. Makarand :August 16, 2022 at 11:06 am
3. Gopal :November 14, 2022 at 5:53 pm