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

- 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
and*first_number*.*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
. If no such index were found means given array is smaller permutation possible, in that case, return the given array.*first_number* - 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
and*first_number*will be our answer for permutation which is largest but smaller than the given permutation.*second_number* - See the walk-through of an example below

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. SoGiven Array: [1, 7, 3, 4, 5]Now find the maximum element from 3, 4, 5which is smaller thanfirst_number = 7., which is 5. So ourfirst_number = 7Swap 5 and 7 impliessecond_number = 5.updated array:which is the largest but smaller than the given permutation [1, 7, 3, 4, 5][1, 5, 3, 4, 7].

Time Complexity: **O(N)**

**Complete Code:**

**Output:**

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