All problems

Next Permutation

Medium · two pointers

A list of numbers nums can be rearranged in many ways. Write down every distinct rearrangement of its values in dictionary order: compare two arrangements by their first number, then by the second if the first numbers are equal, and so on. Arrangements that look the same (because of repeated values) are listed once.

Return the arrangement that comes immediately after nums in that list. If nums is already the last arrangement, return the first one instead, which is all the numbers in ascending order.

The input list is not changed; return a new list.

Examples

Example 1

Input: nums = [2, 4, 3, 1]

Output: [3, 1, 2, 4]

Of the arrangements that start with 3, the smallest is [3, 1, 2, 4], and it is the first one after [2, 4, 3, 1].

Example 2

Input: nums = [3, 2, 1]

Output: [1, 2, 3]

[3, 2, 1] is the last arrangement, so the answer wraps round to the first one.

Example 3

Input: nums = [1, 5, 1]

Output: [5, 1, 1]

The arrangements are [1, 1, 5], [1, 5, 1] and [5, 1, 1], so the next one is [5, 1, 1].

Constraints