Given an array representing a permutation, transform it into the next lexicographically greater permutation. If such a permutation does not exist, rearrange the numbers into the lowest possible order. The answer must be done in-place.
Input: nums = [1,2,3]
Output: [1,3,2]
Explanation: [1,3,2] is the smallest permutation larger than [1,2,3].
Input: nums = [3,2,1]
Output: [1,2,3]
Explanation: The sequence is already the largest, so we wrap to the smallest.
- Scan from the right to find the first dip.
- Suffix to the right of the dip is always non-increasing.
- Swap with the rightmost just-greater element.
- Then reverse the suffix, do not sort it.
- Memory hook: dip, swap, reverse.
Algorithm: Generate all permutations, sort them, and locate the next one.
Pseudo:
- Generate every permutation of the array.
- Sort all permutations lexicographically.
- Find the current permutation and return the next one.
Time: O(n! * n)
Space: Huge
Why mention it: It explains the meaning of the task, but is never acceptable in interview implementation.
Algorithm: Find the break point and sort the suffix after swapping.
Pseudo:
- Find the first index i from the right where nums[i] < nums[i + 1].
- Find the smallest number greater than nums[i] on the right.
- Swap them.
- Sort the suffix from i + 1 to end.
Time: O(n log n)
Space: O(1) extra if the sort is in-place
Interview line: This is acceptable logically, but the suffix is already in descending order, so reverse is enough.
Algorithm: Use one backward scan for the dip, one backward scan for the swap target, then reverse the suffix.
Pseudo:
- Find index i from the right such that nums[i] < nums[i + 1].
- If no such i exists, reverse the whole array and return.
- Find index j from the right such that nums[j] > nums[i].
- Swap nums[i] and nums[j].
- Reverse nums from i + 1 to end.
Time: O(n)
Space: O(1)
Key insight: Reverse works because the suffix is already in descending order before the final step.
allPermutations = generate all permutations of nums
sort allPermutations in lexicographic order
position = index of nums inside allPermutations
IF position is not the last index
RETURN allPermutations[position + 1]
RETURN allPermutations[0]
i = rightmost index such that nums[i] < nums[i + 1]
IF i does not exist
sort nums
RETURN nums
find the smallest value on the right greater than nums[i]
swap it with nums[i]
sort nums from i + 1 to end
RETURN nums
i = rightmost index such that nums[i] < nums[i + 1]
IF i does not exist
reverse whole array
RETURN nums
j = rightmost index such that nums[j] > nums[i]
swap nums[i] and nums[j]
reverse nums from i + 1 to end
RETURN nums