Pattern visualizer
Next Permutation
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. Animated on: nums = [1,3,2] — rearrange into the lexicographically next greater permutation, in place..
Find the pivot, swap with the smallest larger suffix value, reverse the rest
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