Pattern Guide
Next Permutation & Lexicographic Order
"Find next/previous permutation in-place. Kth permutation, all permutations in order."
Next permutation: find the next arrangement in lexicographic order. Algorithm: (1) find rightmost i where nums[i] < nums[i+1], (2) find rightmost j > i where nums[j] > nums[i], (3) swap, (4) reverse [i+1..end]. If no such i (descending order), reverse all. This is an O(n) in-place algorithm. Applications: enumerate permutations in order, kth permutation using factoradic number system.
Problems you can solve with this pattern
4 problems · click any to start solving
function nextPermutation(nums) {
const n = nums.length;
let i = n - 2;
// Step 1: find rightmost i where nums[i] < nums[i+1]
while (i >= 0 && nums[i] >= nums[i+1]) i--;
if (i >= 0) {
// Step 2: find rightmost j > i where nums[j] > nums[i]
let j = n - 1;
while (nums[j] <= nums[i]) j--;
// Step 3: swap
[nums[i], nums[j]] = [nums[j], nums[i]];
}
// Step 4: reverse suffix [i+1..n-1]
let l = i + 1, r = n - 1;
while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }
}Next permutation algorithm: scan from right to find first descent (nums[i] < nums[i+1]). Then from right, find first element greater than nums[i]. Swap them. Reverse the suffix after i (it was descending, becomes ascending = smallest arrangement). Kth permutation: at each position, k determines which digit to place using factorial counting: digit_index = (k-1) / (n-1)!, remainder for next position.
function nextPermutation(nums) {
const n = nums.length;
let i = n - 2;
// Step 1: find rightmost i where nums[i] < nums[i+1]
while (i >= 0 && nums[i] >= nums[i+1]) i--;
if (i >= 0) {
// Step 2: find rightmost j > i where nums[j] > nums[i]
let j = n - 1;
while (nums[j] <= nums[i]) j--;
// Step 3: swap
[nums[i], nums[j]] = [nums[j], nums[i]];
}
// Step 4: reverse suffix [i+1..n-1]
let l = i + 1, r = n - 1;
while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }
}1. Find rightmost i where nums[i] < nums[i+1] (rightmost ascending pair)
2. Find rightmost j where nums[j] > nums[i]
3. Swap nums[i] and nums[j]
4. Reverse suffix from i+1 to end
Why it works: The suffix after i was descending (otherwise i would be higher). After swapping, suffix is still descending. Reversing makes it ascending = smallest arrangement with the new nums[i].
Kth permutation: Factoradic representation. Group permutations by first digit in blocks of (n-1)!. Which block k falls in determines first digit. Recurse on remainder.