Take the numbers in nums and write down every way to arrange them in a row. Sort these rows the way words are sorted in a dictionary: compare the first numbers, then the second numbers, and so on.
For example, the arrangements of 1, 5 and 9 in dictionary order are [1,5,9], [1,9,5], [5,1,9], [5,9,1], [9,1,5] and [9,5,1]. The row after [5,1,9] is [5,9,1]. After the very last row, [9,5,1], the list wraps around to the first row, [1,5,9].
Change nums into the row that comes right after it. Do this in place, and use only a constant amount of extra memory. Numbers may repeat. The next row is then the smallest row that is bigger than the current one.
Examples
Example 1:
Input: nums = [2,6,3,1]
Output: [3,1,2,6]
Explanation: In dictionary order, the row right after [2,6,3,1] is [3,1,2,6].
Example 2:
Input: nums = [4,3,2,1]
Output: [1,2,3,4]
Explanation: This is the last row, so the list wraps around to the first row, which is sorted from small to big.
Example 3:
Input: nums = [4,2,7,5,1]
Output: [4,5,1,2,7]
Explanation: In dictionary order, the row right after [4,2,7,5,1] is [4,5,1,2,7].