Next Permutation
You get an integer array nums. Think of every way to arrange its numbers, and put those arrangements in dictionary order (compare the first position, then the second, and so on).
Return the arrangement that comes right after nums in that order. If nums is already the last (largest) arrangement, return the first one instead, which is the numbers sorted from smallest to largest.
The array can contain the same number more than once. Arrangements that look the same count as one arrangement.
Return the new array. You may change nums and return it, or build a new array.
Hint
Walk from the right end. Find the first position where a number is smaller than the number after it. Everything to the right of that position is in non-increasing order. Which number should take its place, and how should the right part look afterwards?
Examples
Example 1
- Input:
- [2,4,3,1]
- Output:
- [3,1,2,4]
From the right, 2 is the first number smaller than the one after it. The smallest number on its right that is bigger than 2 is 3. Put 3 first, then the rest (1, 2, 4) in ascending order.
Example 2
- Input:
- [5,4,4,1]
- Output:
- [1,4,4,5]
The numbers never go up from left to right, so this is the largest arrangement. The answer wraps to the smallest one: the sorted array.
Example 3
- Input:
- [1,2,2]
- Output:
- [2,1,2]
The arrangements in order are [1,2,2], [2,1,2], [2,2,1]. The one after [1,2,2] is [2,1,2].
Constraints
1 <= nums.length <= 80 <= nums[i] <= 9- Aim for O(n) time and O(1) extra space.
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.