20. Next Permutation

Medium · Array

Given an array of integers, modify it in-place to represent the next lexicographically greater permutation. If the array is already the largest permutation, wrap around to the smallest (first) permutation.

A permutation is a rearrangement of all elements. The next lexicographically greater permutation is the smallest permutation that is larger than the current one when compared element-by-element from left to right.

Examples

Example 1
Input: [1, 2, 3]
Output: [1, 3, 2]
Explanation: The permutations of [1, 2, 3] in order are: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. The next permutation after [1, 2, 3] is [1, 3, 2].
Example 2
Input: [3, 2, 1]
Output: [1, 2, 3]
Explanation: [3, 2, 1] is the largest permutation, so it wraps around to [1, 2, 3], the smallest permutation.

Constraints