Permutation Before One Swap

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in company
Accolite

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
1 2 1
2
6 2
Sample Output 1 :
1 1 2
2 6
Explanation Of Sample Input 1 :
In the first test case, we can swap ARR[1] and ARR[2] (0 based index) to obtain permutation [1,1,2]  which is lexicographically largest permutation smaller than [1, 2, 1].

In the second test case, we can swap ARR[0] and ARR[i] to obtain permutation [2, 6],  [2, 6] which is lexicographically largest permutation smaller than [6, 2].
Sample Input 2 :
2
3
3 2 1
4
1 2 4 3
Sample Output 2 :
3 1 2
1 2 3 4
Hint

Swap each pair of integers in ‘ARR’.

Approaches (2)
Brute Force

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:

  1. Make an empty integer list/array ‘RESULT’
  2. 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’.

Time Complexity

O(N^3), where 'N' is the size of ‘ARR’.


There are O(N^2) pairs of indexes in ‘ARR’ and it takes O(N) time in each iteration to do a lexicographical comparison of ‘ARR’ after swapping elements with ‘RESULT’. Thus, the overall time complexity will be O(N^3).

Space Complexity

O(1)

 

We are using constant extra space here.

Code Solution
(100% EXP penalty)
Permutation Before One Swap
Full screen
Console