This post is completed by 1 user

  • 1
 Add to List
Medium

437. 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.

Example:

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]

Approach:

  1. 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.
  2. Let's say these two elements are first_number and second_number.
  3. 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.
  4. 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. 
  5. Swapping  first_number and second_number will be our answer for permutation which is largest but smaller than the given permutation.
  6. 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)

Output:

Given Array: [1, 7, 3, 4, 5]
Largest permutation smaller than given array: [1, 5, 3, 4, 7]

Related Problems: