Next Permutation
Rearrange nums into the next lexicographically greater permutation in place. If none exists, wrap to the smallest (ascending) arrangement.
Intuition
Scanning from the right, find the first place where order dips — that pivot is the digit we can grow. Swap it with the smallest value to its right that still beats it, then reverse the tail so it becomes the smallest possible suffix.
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
Enumerating permutations is hopeless
Listing all n! permutations to find the one after the current arrangement is astronomically slow. Instead we reason directly about what 'the next larger arrangement' means lexicographically, like finding the next number with the same digits — and that turns out to need just three local operations.
Find the pivot: the first dip from the right
Scan from the right for the first index i where nums[i] < nums[i+1]. Everything to the right of i is in descending order, which means that suffix is already the largest it can be — you can't make the number bigger by rearranging only the suffix. So the digit that must increase is nums[i], the pivot. (If no such i exists, the whole array is descending — it's the largest permutation, and the answer wraps to the smallest.)
Swap minimally, then reset the tail
To grow the number by the smallest possible amount, swap the pivot with the smallest value to its right that still exceeds it — found by scanning from the far right for the first nums[j] > nums[i]. After the swap, the suffix is still descending; since we want the smallest tail following the increased pivot, reverse that suffix into ascending order. Pivot-find, swap, reverse — all O(n), O(1) space, in place.
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.