Rearrange an array into the next lexicographically greater permutation, or the smallest permutation if none exists.
Problem
Given an array of integers representing a permutation, rearrange the numbers in place so that they form the next lexicographically greater permutation.
If such a permutation does not exist, rearrange the array into the lowest possible order (sorted in ascending order).
A permutation is lexicographically smaller than permutation if at the first position where they differ, has a smaller value than .
Your task is to modify the input array directly and produce the next permutation in this ordering.
Notes
- The result must use the same elements exactly once each.
- You should aim for an time solution and constant extra space.
Input Format
- An integer array
numsof lengthn. numsrepresents one permutation of some set of values.- The array should be modified in place.
Output Format
- Return or update
numsso it becomes the next lexicographically greater permutation. - If no greater permutation exists, transform it into the smallest permutation.
Constraints
- All elements are comparable for ordering.
- Use constant extra space if possible.
- Target linear time complexity.
Example 1
Input
nums = [1,2,3]
Output
[1,3,2]
Explanation
The next permutation after [1,2,3] is [1,3,2].
Example 2
Input
nums = [3,2,1]
Output
[1,2,3]
Explanation
This is the last permutation, so the array is rearranged into the smallest order.
Show 1 more example
Example 3
Input
nums = [1,1,5]
Output
[1,5,1]
Explanation
Among distinct lexicographic permutations, [1,5,1] is the next one after [1,1,5].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.