How Does the Next Permutation Algorithm Work?
Learn the O(n) in-place next permutation algorithm: pivot, swap, and reverse, with Python code and interview tips.
Expected Interview Answer
The next permutation algorithm rearranges a sequence in place into the lexicographically next greater permutation using O(n) time and O(1) extra space, by finding the rightmost ascending pair, swapping it with the smallest larger value to its right, and reversing the suffix.
Scan from the right to find the first index i where nums[i] < nums[i+1] — this is the rightmost position where increasing the sequence is still possible, because everything to its right is already in fully descending (locally maximal) order. If no such i exists, the whole array is descending, meaning it is the last permutation, so you simply reverse the entire array to wrap around to the first (smallest) permutation. Otherwise, scan from the right again to find the smallest value greater than nums[i] within the suffix (guaranteed to exist since nums[i+1] alone already qualifies), swap it with nums[i], then reverse the suffix starting at i+1 to put it back into ascending (smallest possible) order. The reversal step is what makes the result the *next* permutation rather than just *a* larger one — since the suffix was descending before the swap, and stays a permutation of the same multiset after it, sorting it ascending yields the smallest possible arrangement of that remaining suffix.
- O(n) time, O(1) extra space — fully in place
- Generates permutations in strict lexicographic order without storing all of them
- Wraps around cleanly from the last permutation to the first
- Core building block for combinatorial enumeration and backtracking problems
AI Mentor Explanation
Think of a fixed batting lineup written as a sequence of jersey numbers, and you want the very next lineup in alphabetical-style ordering that is still lexicographically greater than the current one. Scan from the end of the lineup to find the first spot where a player's number is smaller than the one right after it — everything past that spot is already arranged from highest to lowest, the most 'exhausted' ordering possible for that tail. Swap that spot's player with the smallest-numbered player further down the lineup who still outranks them, then flip the entire remaining tail from highest-to-lowest into lowest-to-highest. That flip is essential: it turns the already-maximal tail into the smallest possible tail, guaranteeing you land on the immediate next lineup rather than skipping ahead.
Step-by-Step Explanation
Step 1
Find the pivot from the right
Scan right to left for the first index i where nums[i] < nums[i+1]; the suffix after i is already descending.
Step 2
Handle the fully descending case
If no such i exists, the array is the last permutation — reverse the whole array to wrap to the first permutation.
Step 3
Find the successor and swap
Scan the descending suffix from the right for the smallest value greater than nums[i], and swap it with nums[i].
Step 4
Reverse the suffix
Reverse everything after index i to turn the still-descending suffix into ascending (smallest) order, yielding the true next permutation.
What Interviewer Expects
- Correctly identify the pivot as the rightmost ascending pair
- Explain why the suffix after the pivot is guaranteed descending before the swap
- Justify why reversing the suffix (not just leaving it) is required for correctness
- State O(n) time and O(1) extra space
Common Mistakes
- Forgetting to reverse the suffix after swapping, which gives a larger permutation but not the immediate next one
- Picking any larger value in the suffix instead of the smallest one greater than nums[i]
- Not handling the edge case where the array is already the last (fully descending) permutation
- Using extra space to generate and sort all permutations instead of the O(1)-space in-place technique
Best Answer (HR Friendly)
“I would scan from the right to find the last place where the sequence increases, since everything after that is already in its most 'used up', fully descending state. Then I would swap that spot with the smallest number further right that is still bigger than it, and finally reverse everything after that spot so it goes back to being the smallest possible arrangement. That combination gives the exact next permutation in order.”
Code Example
def next_permutation(nums):
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i == -1:
nums.reverse()
return
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# Example: [1, 2, 3] -> [1, 3, 2]; [3, 2, 1] -> [1, 2, 3]
arr = [1, 2, 3]
next_permutation(arr)
print(arr)Follow-up Questions
- How would you find the previous permutation instead of the next?
- How would you generate all permutations of an array using this technique repeatedly?
- How does this algorithm handle duplicate values in the input?
- What is the total time to enumerate all n! permutations by repeatedly calling next_permutation?
MCQ Practice
1. What is the next permutation of [1, 3, 2]?
The pivot is index 0 since 1 < 3. The smallest suffix value greater than 1 is 2, so swapping gives [2, 3, 1]. Reversing the suffix after the pivot turns [3, 1] into [1, 3], producing the final answer [2, 1, 3].
2. What should next_permutation do when the input is already the last permutation (fully descending)?
A fully descending array has no ascending pivot, so the algorithm wraps around by reversing to the smallest permutation.
3. What is the space complexity of the standard in-place next permutation algorithm?
The algorithm swaps and reverses elements in place using only a few index variables, giving O(1) extra space.
Flash Cards
What is the first step of the next permutation algorithm? — Scan from the right to find the first index i where nums[i] < nums[i+1] (the pivot).
What happens if no pivot is found? — The array is the last permutation; reverse it entirely to wrap to the first (smallest) permutation.
What is swapped with the pivot? — The smallest value in the suffix that is still greater than nums[i].
Why must the suffix be reversed after the swap? — The suffix was descending before the swap; reversing it to ascending yields the smallest possible tail, guaranteeing the immediate next permutation.