Given a permutation of numbers in the form of an array ` arr `

, find the immediate next lexicographically greater permutation. If the next lexicographically greater permutation is not possible, print the permutation as is.

#### Example Test Cases

##### Sample Test Case 1

Input Array: ` [1, 2, 3 ] `

Expected Output: ` [1, 3, 2 ] `

Explanation: The next lexicographically greater permutation is [1, 3, 2]

##### Sample Test Case 2

Input Linked List: ` [4, 3, 7, 6 ] `

Expected Output: ` [4, 6, 3, 7 ] `

#### Solution

To find the next lexicographic permutation of these numbers, we would need to swap two numbers from index ` i `

and index ` j `

such that ` j > i `

and ` arr[j] > arr[i] `

.

To find the just next lexicographic permutation, we would want to increase ` i `

as much as possible and minimize ` arr[j] `

for example, in the sample test case 2 ` [4, 3, 7, 6 ] `

, we could have swapped element at position ` i = 0 `

with element at position ` j = 3 `

which would have given us permutation ` [6, 3, 7, 4] `

Clearly this is not the optimal solution. Therefore, we will swap element at position ` i = 1 `

with element at position ` j = 3 `

(to maximize ` i `

and minimize ` arr[j] `

). To further minimize the permutation we will sort the array from position ` (i + 1 `

onwards, which will give us the desired answer.

See the below code for implementation.

### Implementation

#include <bits/stdc++.h> using namespace std; // Finds the smallest element which is located after position l and is larger than arr[l]; int findNextLargerElement(vector& arr, int l) { int soFar = -1; for(int j = l + 1; j < arr.size(); j++) { if (arr[j] > arr[l]) { if (soFar == -1) { soFar = j; } else if (arr[j] < arr[soFar]) { soFar = j; } } } return soFar; } void swap(vector& arr, int i , int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void nextPermutation(vector& arr) { bool flag = false; int pos = -1; int minSoFar = arr.size() - 1; int maxSoFar = arr.size() - 1; // loop to find the position which should be swapped. for(int i = arr.size() - 2; i >= 0 && !flag; i--) { if (arr[i] < arr[minSoFar]) { swap(arr, i, minSoFar); pos = i + 1; flag = true; } else if (arr[i] >= arr[minSoFar] && arr[i] < arr[maxSoFar]) { int mi = findNextLargerElement(arr, i); swap(arr, i, mi); pos = i + 1; flag = true; } if (arr[i] < arr[minSoFar]) { minSoFar = i; } if (arr[i] > arr[maxSoFar]) { maxSoFar = i; } } if (!flag) { sort(arr.begin(), arr.end()); } else { sort(arr.begin() + pos, arr.end()); } } int main() { vector arr = { 4, 3, 7, 6 }; nextPermutation(arr); cout << "Next permutation is \n"; for(int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } cout << "\n"; }