Lexicographically previous permutation With One swap
Objective: Given an array of integers (in particular order or permutation of a set of numbers), write an algorithm to find the lexicographically previous permutation of the given permutation with only one swap.
This problem can also be asked as “Given a permutation of numbers you need to find the next smaller premutation OR largest permutation which is smaller than the given permutation”
Note: In the case given permutation is smallest, return the given permutation.
Given Array: [1, 7, 3, 4, 5] Largest permutation smaller than a given array: [1, 5, 3, 4, 7] Given Array: [1, 2, 3, 4, 5] Original Array is already the smallest permutation: [1, 2, 3, 4, 5] Given Array: [4, 2, 5, 6] Largest permutation smaller than a given array: [2, 4, 5, 6]
- We need to find the two numbers so that swapping these numbers will produce the permutation which is largest but smaller than the given permutation.
- Let’s say these two elements are first_number and second_number.
- Iterate the given array from right to left and find the first index where the left element is greater than the right element. Once found, the element at the left index will be our first_number. If no such index were found means given array is smaller permutation possible, in that case, return the given array.
- Now find the maximum element (which is smaller than first_number) from the right element(found in the previous step) to the end of the array. This maximum element will be our second_number.
- Swapping first_number and second_number will be our answer for permutation which is largest but smaller than the given permutation.
- See the walk-through of an example below
Given Array: [1, 7, 3, 4, 5]
Iterate the given array from right to left and find the first index where left element is greater than the right element. So in the given array 7>3. So first_number = 7.
Now find the maximum element from 3, 4, 5which is smaller than first_number = 7, which is 5. So our second_number = 5.
Swap 5 and 7 implies updated array: [1, 5, 3, 4, 7] which is the largest but smaller than the given permutation [1, 7, 3, 4, 5].
Time Complexity: O(N)
Given Array: [1, 7, 3, 4, 5] Largest permutation smaller than given array: [1, 5, 3, 4, 7]
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.