Last Updated: 10 Apr, 2021

Permutation Before One Swap

Moderate

Asked in company

Solve now

Problem statement

You are given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to find and return the lexicographically largest permutation of ‘ARR’ that is smaller than ‘ARR’ and that can be made by swapping the position of any two integers of ‘ARR’ at different indexes exactly once.

Note :

1. It is guaranteed that there will exist a permutation of ‘ARR’ which is lexicographically smaller than ‘ARR’.
2. All integers of ‘ARR’ are not necessarily distinct.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’, representing the size of ‘ARR’ 

The second line of each test case will contain ‘N’ space-separated integers representing array/list ‘ARR’.

Output Format :

For each test case, print ‘N’ space-separated integers representing the lexicographically largest permutation of ‘ARR’ that is smaller than ‘ARR’ and that can be made by swapping the position of any two integers of ‘ARR’ at different indexes exactly once.

Output for every test case will be printed in a separate line.

Note :

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
2 <= N <= 10000
1 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the 'ith'element of ARR.

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to make an empty integer list/array ‘RESULT’ and try out each permutation that can be obtained by exactly one swap and then compare each of them with ‘ARR’. If the current permutation is lexicographically smaller than ‘ARR’ and lexicographically larger than ‘RESULT’ then makes ‘RESULT’ equal to the current permutation.

The steps are as follows:

Make an empty integer list/array ‘RESULT’
Run a loop where ‘i’ ranges from 0 to ‘N’-1 and for each ‘i’ do the following -:
1. Run a loop where ‘j’ ranges from ‘i’+1 to ‘N’-1 and do the following -:
  1. If ‘ARR[i]’ ≤ ‘ARR[j]’, then skip this iteration, because swapping ‘ARR[i]’ and ‘ARR[j]’ gives permutation larger pr equal to the current ‘ARR’.
  2. Swap ‘ARR[i]’ with ‘ARR[j]’.
  3. Do ‘RESULT’:= max(‘RESULT’, ‘ARR’). Note, max here finds the lexicographically largest permutation among both.
  4. Swap ‘ARR[i]’ with ‘ARR[j]’ to restore the original array.

Return ‘RESULT’.

Solve now

02 Approach

We move from the right side of the array/list ‘ARR’ toward the left side until the point where the element is larger than its right neighbour element. Let the index of this element be ‘i’

At this point, ‘ARR[i]’ is one of the elements that should be swapped.

We actually need to swap ‘ARR[i]’ with the largest element on its right side that is less than it. If there are multiple such elements we find the element closest to index ‘i’.

The steps are as follows:

Run a loop where ‘i’ ranges from ‘N’-2 to 0 and for each ‘i’ do the following -:
1. If ‘ARR[i]’ <= ‘ARR[i+1]’, then skip this iteration.
2. Initialize an integer ‘p’ := ‘i’+1.
3. Run a loop where ‘j’ ranges from ‘i+1’ to ‘N-1.
  1. If ARR[j] < ARR[i] and ARR[j] > ARR[p]:
    1. Do ‘p’ := j.
4. Swap ‘ARR[p]’ with ‘ARR[i]’.
5. Break the loop.
Return ‘ARR’.

Solve now