# 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:**

- 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.
- Let’s say these two elements are
and*first_number*.*second_number* - 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
. If no such index was found means the given array is the largest permutation possible, in that case return the given array.*first_number* - Now find the minimum element (which is greater than
) from the right element(found in the previous step) to the end of the array. This minimum element will be our*first_number*.*second_number* - Swap
and*first_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.*second_number* - 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 =

**which is the smallest but greater than the given permutation [4, 2, 5, 1, 0].**

*[4, 5, 0, 1, 2]*Time Complexity: **O(nlogn)**

**Complete Code:**

**Output:**

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