Next Permutation
Find the pivot, swap with the smallest larger suffix value, reverse the rest
The suffix of a permutation that's already in decreasing order can't be rearranged into anything bigger — it's already at its max. So scan from the right for the first spot where the sequence still increases (the pivot); that digit CAN be replaced by something bigger. Swap it with the smallest value in the suffix that's still larger than it, then reverse the suffix (now guaranteed decreasing) to make it as small as possible — giving the smallest possible increase overall.
Details
Animated on: nums = [1,3,2] — rearrange into the lexicographically next greater permutation, in place.
Problem:Next PermutationMedium
Find the pivot, swap with the smallest larger suffix value, reverse the rest
step 1 / 6
Scan from the right to find the first place the sequence drops — that's the digit we need to bump up.
1FUNCTION nextPermutation(nums):2 set i to (the length of nums) - 23 WHILE i >= 0 and nums[i] >= nums[i+1]: move i one step left (find the pivot)4 IF i >= 0:5 find the rightmost j where nums[j] > nums[i]6 swap nums[i] and nums[j]7 reverse the part of nums after position i (makes the smallest suffix)
← / → step · space play · Home restart
Every step in words
Show all 6 steps
- Scan from the right to find the first place the sequence drops — that's the digit we need to bump up.
- i=0 (value 1) is the last index where nums[i] < nums[i+1] — everything after it is non-increasing.
- j=2 (value 2) is the rightmost value still greater than nums[i]=1 — the smallest such value works, found by scanning from the right.
- Swap nums[0] and nums[2] -> [2, 3, 1]. This bumps the prefix to the next bigger value.
- Reverse the suffix after i (indices 1..2) so it becomes the smallest possible arrangement — it was non-increasing, so reversing makes it non-decreasing.
- Suffix reversed. The next permutation after [1, 3, 2] is [2, 1, 3].
Now solve it yourself
Watching is the first half. The second is writing it without the animation.