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

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

Tanishq Chaudhary

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