DIY: Next Permutation

Solve the interview question "Next Permutation" in this lesson.

Problem statement

Given a list of numbers, you have to rearrange these numbers into the next lexicographically greater permutation of numbers. If such an arrangement is not possible, you must rearrange it to the lowest possible order (that is, sort it in ascending order).

Note: You need to ensure an in-place replacement of the numbers and use only constant extra memory.

Input

The input is a list of numbers.

[4,5,2,6,7,3,1] 

Output

The output should be the same numbers, rearranged in the next lexicographically greater permutation. The following is the example output of the input from above:

[4,5,2,7,1,3,6]

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.