Medium
Next Permutation
- Time limit
- 2 s
- Memory limit
- 256 MB
- Estimated
- 20 min
- Subsets, Permutations and Combinations
Description
Description
Given an integer array nums, compute the next permutation of its elements in lexicographic order: the smallest arrangement that is strictly greater than the current one, considering all permutations of the multiset of values as sorted lexicographically. If nums is already the last (fully descending) permutation, return the first (fully ascending) permutation instead.
Examples
Example 1
- Input:
nums = [1, 2, 3] - Output:
[1, 3, 2]
Example 2
- Input:
nums = [3, 2, 1] - Output:
[1, 2, 3]
Example 3
- Input:
nums = [1, 1, 5] - Output:
[1, 5, 1]
Expected Function Behavior
Implement nextPermutation(nums) and return the resulting array.
Constraints
1 <= nums.length <= 100000-1000000000 <= nums[i] <= 1000000000
Sample cases
3Sample 1
Input
nums = [1,2,3]
Expected output
[1,3,2]
Sample 2
Input
nums = [3,2,1]
Expected output
[1,2,3]
Skills and languages
Concepts
- Next Permutation
Patterns
- Two Pointers
Languages
- Python 3
Solve this problem
Create a free account to write, run and submit your solution.
- Write Python or Java in the browser, with your draft saved as you type
- Run your code on the examples as often as you like
- Submit to a sandboxed judge and see exactly which case failed
- Ask the AI mentor for a hint without being handed the answer