Next Permutation
Rearrange nums into the next lexicographically greater permutation in place. If none exists, wrap to the smallest (ascending) arrangement.
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
Intuition
Next permutation rearranges numbers into the next lexicographically greater arrangement, in place and with O(1) extra memory. Generating permutations to find the successor is far too slow; the answer is a short sequence of steps.
The structure comes from noticing that a suffix in descending order is already the largest arrangement of its elements — nothing greater can be made without changing something earlier:
- Scan from the right for the first index i where nums[i] < nums[i + 1] — that element is the pivot, the rightmost position that can be increased.
Everything after the pivot is descending by construction, since the scan stopped at the first ascent.
To make the smallest possible increase, the pivot must be swapped with the smallest element to its right that still exceeds it. Because the suffix is descending, scanning from the right for the first element greater than the pivot finds exactly that value — no sorting needed.
After the swap the suffix remains descending, so it is still the largest arrangement of those elements. Reversing it makes it the smallest, which gives the immediate successor rather than a distant one.
That reversal is the step most often forgotten, and it produces a valid but far-too-large permutation.
If no pivot exists, the entire array is descending — the last permutation. The problem then requires wrapping to the first, which is the fully ascending order, obtained by reversing the whole array.
All three steps are linear scans with in-place swaps, giving O(n) time and O(1) space.
Three moves: find the rightmost ascent nums[i] < nums[i+1], swap nums[i] with the smallest value to its right that still exceeds it, then reverse the suffix. The suffix after the pivot is always non-increasing, which is why reversing — not sorting — restores it to its smallest arrangement.
Approach
Before reading on: price up what enumerating every case costs here, then ask what makes it safe to discard one end without checking it against everything. Aim for O(n) time and O(1) space.
Find the pivot from the right
Scan right to left for the first index where nums[i] < nums[i + 1]. Everything after it is descending, already the largest arrangement of those elements.
Handle the fully descending case
No pivot means the array is the last permutation. Reverse the whole array to wrap around to the first, as the problem requires.
Find the swap target
Scan from the right for the first element greater than the pivot. The descending suffix guarantees this is the smallest such value, so no sorting is needed.
Swap them
Exchange the pivot with that element. This is the smallest possible increase at the rightmost position that can be increased.
Reverse the suffix
The suffix is still descending after the swap, so reversing makes it the smallest arrangement. Omitting this yields a valid but far-too-large permutation.
Cost of the approach
Three linear scans with in-place swaps give O(n) time and O(1) space, meeting the problem's memory requirement exactly.
Solution & live demo
Common pitfalls
Sorting the suffix instead of reversing it
nums[i+1:] = sorted(nums[i+1:])
nums[i+1:] = reversed(nums[i+1:])
Correct output, but wasteful. By construction the suffix is already in non-increasing order and the swap preserves that, so reversing gives the sorted order in O(n) instead of O(n log n).
Not handling the fully descending case
j = n - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i]
if i >= 0:
j = n - 1
while nums[j] <= nums[i]: j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1:] = reversed(nums[i+1:])On [3, 2, 1] no ascent exists and i lands at -1. Swapping then corrupts the array, when the correct answer is simply to reverse the whole thing into [1, 2, 3]. The reverse must run unconditionally; only the swap is guarded.
Using < when scanning for the swap partner
while nums[j] < nums[i]: j -= 1
while nums[j] <= nums[i]: j -= 1
With duplicates, stopping at a value equal to the pivot produces a swap that changes nothing, so the permutation doesn't advance. The partner must be strictly greater.
Edge cases
No pivot is found (i falls below 0); the suffix reverse then turns the whole array ascending — the smallest permutation.
No pivot, no swap; reversing a length-1 suffix leaves it unchanged.
The >=/<= comparisons pick the correct pivot and swap target even with repeats.