This post is completed by 2 users

  • 1
 Add to List
Medium

466. Lexicographically next 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 next 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 larger permutation OR smallest permutation which is greater than the given permutation".  

Note: In the case given permutation is largest, return the given permutation.

Example:

Given Array: [1, 7, 3, 4, 5]
smallest permutation greater than given array: [1, 7, 3, 5, 4]

Given Array: [5, 4, 3, 2, 1]
Original Array is already the largest possible permutation: [5, 4, 3, 2, 1]

Given Array: [4, 2, 5, 1, 0]
smallest permutation greater than given array: [4, 5, 0, 1, 2]

Approach:

  1. We need to find the two numbers so that swapping these numbers will produce the permutation which is the smallest but larger 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 smaller than the right element. Once found, the element at the left index will be our first_number. If no such index was found means the given array is the largest permutation possible, in that case return the given array.
  4. Now find the minimum element (which is greater than first_number) from the right element(found in the previous step) to the end of the array. This minimum element will be our second_number. 
  5. Swap  first_number and second_number and sort the rest of the array (from next index to end of the array) and this will be our answer for permutation which is the smallest but greater than the given permutation.
  6. See the walk-through of an example below 

Given Array: [4, 2, 5, 1, 0]

Iterate the given array from right to left and find the first index where the left element is smaller than the right element. So in the given array 2<5. So first_number = 2.

Now find the minimum element from 5, 1, 0 which is greater than first_number = 2, which is 5. So our second_number = 5.  

Swap 2 and 5 implies updated array:  [4, 5, 2, 1, 0] 

sort the rest of the array (from next index to end of the array so sort 2, 1, 0). Result = [4, 5, 0, 1, 2]  which is the smallest but greater than the given permutation [4, 2, 5, 1, 0].

Time Complexity: O(nlogn)

Output:

Given Array: [4, 2, 5, 1, 0]
smallest permutation greater than given array: [4, 5, 0, 1, 2]

Related Problems: