Search

# Next Permutation - Interviewbit Solution

Problem: Next Permutation

Problem Description:

Implement the next permutation, which rearranges numbers into the numerically next greater permutation of numbers for a given array A of size N.

If such arrangement is not possible, it must be rearranged as the lowest possible order i.e., sorted in an ascending order.

Note:

```1. The replacement must be in-place, do **not** allocate extra memory.
2. DO NOT USE LIBRARY FUNCTION FOR NEXT PERMUTATION. Use of Library
functions will disqualify your submission retroactively and will
give you penalty points.```

Input Format:

`The first and the only argument of input has an array of integers, A. `

Output Format:

`Return an array of integers, representing the next permutation of the given array. `

Constraints:

```1 <= N <= 5e5
1 <= A[i] <= 1e9```

Examples:

```Input 1:
A = [1, 2, 3]
Output 1:
[1, 3, 2]```
```Input 2:
A = [3, 2, 1]
Output 2:
[1, 2, 3]```
```Input 3:
A = [1, 1, 5]
Output 3:
[1, 5, 1]```
```Input 4:
A = [20, 50, 113]
Output 4:
[20, 113, 50]```

Solution:

Tags: