Next Permutation: Sort Suffix Skips 40% of Permutations
40% of permutations skipped: sorting suffix in next_permutation breaks duplicates and is 5x slower than reverse.
- Step 1: Find rightmost index i where arr[i] < arr[i+1]. This is the pivot.
- Step 2: Find rightmost j > i where arr[j] > arr[i]. Swap arr[i] and arr[j].
- Step 3: Reverse the suffix starting at arr[i+1]. This makes it ascending (smallest ordering).
- If no pivot exists (array fully descending), reverse entire array to wrap around.
- O(n) time, O(1) space. In-place. No extra memory.
- C++ STL std::next_permutation uses this exact algorithm.
- Test generators use it to enumerate all n! permutations in lexicographic order.
- Sorting the suffix instead of reversing it. The suffix is already descending — reversing is O(n), sorting is O(n log n).
Next permutation finds the lexicographically next greater arrangement of a sequence in O(n) time and O(1) space. It powers C++'s std::next_permutation, Python's itertools.permutations ordering, and Java's Arrays.sort permutation enumeration.
The algorithm has three steps: find the rightmost pivot where arr[i] < arr[i+1], swap it with the next-larger element to its right, then reverse the suffix. The suffix is always descending before the swap — reversing it (not sorting) produces the smallest ordering, which gives the immediately-next permutation.
The common misconception is that you need to generate all permutations to find the next one. You do not. The three-step algorithm computes the next permutation directly from the current arrangement, without enumeration. This is what makes it O(n) instead of O(n!).
What is Next Permutation? — Plain English
Next Permutation rearranges a sequence of numbers into the lexicographically next greater permutation. If no such permutation exists (the sequence is in descending order), it rearranges to the smallest permutation (ascending order).
Example: next permutation of [1, 2, 3] is [1, 3, 2]. Next after [3, 2, 1] is [1, 2, 3] (wraps around). This algorithm solves this in O(n) time and O(1) space, without generating all permutations.
How Next Permutation Works — Step by Step
- Find the largest index i such that arr[i] < arr[i+1]. This is the 'pivot' — the rightmost element that is not part of a descending suffix. If no such i exists, the entire array is in descending order: reverse it and return.
- Find the largest index j > i such that arr[j] > arr[i]. This is the smallest element to the right of the pivot that is larger than the pivot.
- Swap arr[i] and arr[j].
- Reverse the suffix starting at arr[i+1]. The suffix was in descending order before the swap and remains descending after it. Reversing it makes it ascending, giving the smallest possible ordering of the suffix.
Time: O(n). Space: O(1).
Worked Example — Tracing the Algorithm
Input: [1, 3, 5, 4, 2]
Step 1 — Find pivot (largest i where arr[i] < arr[i+1]): Compare from right: arr[3]=4 > arr[4]=2 (no). arr[2]=5 > arr[3]=4 (no). arr[1]=3 < arr[2]=5. YES! pivot i=1.
Step 2 — Find largest j > 1 where arr[j] > arr[1]=3: Right to left: arr[4]=2 < 3 (no). arr[3]=4 > 3 (yes!). j=3.
Step 3 — Swap arr[1] and arr[3]: [1, 3, 5, 4, 2] -> [1, 4, 5, 3, 2]
Step 4 — Reverse suffix from index 2: Suffix [5, 3, 2] reversed -> [2, 3, 5]. Result: [1, 4, 2, 3, 5]
Verification: [1, 4, 2, 3, 5] is the next permutation after [1, 3, 5, 4, 2] in lexicographic order.
Implementation
The algorithm modifies the array in-place in four steps: find the rightmost pivot where arr[i] < arr[i+1], find the rightmost element greater than the pivot, swap them, then reverse the suffix. The suffix is always in descending order before the operation; reversing it makes it ascending — giving the smallest possible ordering of those elements, which produces the immediately-next permutation overall.
| Aspect | Next Permutation (In-Place) | Generate All Permutations (Recursive) | std::next_permutation (C++ STL) | Sort Suffix (Wrong) |
|---|---|---|---|---|
| Time per permutation | O(n) | O(n) per generation | O(n) | O(n log n) |
| Space | O(1) | O(n) recursion stack | O(1) | O(1) |
| Handles duplicates | Yes — strict comparisons | Yes — with dedup set | Yes — strict comparisons | No — unstable sort changes order |
| Enumeration order | Lexicographic (guaranteed) | Depends on implementation | Lexicographic (guaranteed) | Lexicographic (but skips duplicates) |
| Memory for n! permutations | O(n) — one at a time | O(n! * n) — all stored | O(n) — one at a time | O(n) — one at a time |
| Wrap-around | Reverse entire array | N/A (generates all) | Returns false | Reverse entire array |
| Suffix operation | Reverse O(k) | N/A | Reverse O(k) | Sort O(k log k) |
| Duplicate stability | Stable — preserves relative order | Needs dedup | Stable | Unstable — skips permutations |
| Use case | On-demand enumeration | Need all at once | C++ standard library | Never use — bug |
Key Takeaways
- Next permutation finds the lexicographically next arrangement in O(n) time and O(1) space.
- Algorithm: find rightmost pivot where arr[i] < arr[i+1], swap with next-larger element, reverse suffix.
- If the array is entirely descending, reverse the whole array to get the smallest permutation.
- The reversed suffix becomes ascending — the smallest possible ordering of those elements.
- Apply repeatedly to enumerate all permutations of a sequence in lexicographic order.
- Always reverse the suffix, never sort. Reverse is O(k) and stable. Sort is O(k log k) and unstable for duplicates.
- Use strict comparisons (< and >) for pivot and successor search. Non-strict (<= and >=) breaks for duplicates.
- The descending suffix invariant is what makes reverse correct. The suffix is already sorted (descending).
Interview Questions on This Topic
- QWhat are the four steps of the next permutation algorithm?
- QWhat happens when the input array is in descending order?
- QWhy is reversing the suffix (not sorting it) sufficient after the swap?
- QWalk me through the trace for [1, 3, 5, 4, 2]. What is the pivot? What is the successor?
- QHow does the algorithm handle duplicate elements? What goes wrong with non-strict comparisons?
- QWhat is the time and space complexity? Why is it O(n) and O(1)?
- QHow would you enumerate all unique permutations of [1, 2, 2] in lexicographic order?
- QHow would you implement hasNextPermutation to check if a next permutation exists?
- QWhat is the k-th permutation problem? How does it differ from next_permutation?
- QA test generator uses next_permutation but produces duplicate permutations for arrays with repeated elements. Walk me through your debugging process.
Frequently Asked Questions
Why does reversing the suffix after the swap give the next permutation?
The suffix to the right of the pivot was in descending order (that's why we stopped there in step 1). After swapping the pivot with the next-larger element, the suffix is still in descending order (since we swapped with the smallest element larger than the pivot). A descending suffix is the largest arrangement of those elements. Reversing it makes it ascending — the smallest arrangement — giving the overall next-larger permutation.
How would you generate all permutations in lexicographic order?
Start with the sorted array and repeatedly apply next_permutation until you wrap back to the sorted array. This generates all n! permutations in lexicographic order in O(n * n!) total time.
What is the time complexity?
O(n). Step 1 scans at most n-1 elements. Step 2 scans at most n-1 elements. Step 3 is O(1). Step 4 reverses at most n-1 elements. All operations are in-place with O(1) extra space.
Why not sort the suffix instead of reversing it?
The suffix is already in descending order after the swap. Reversing a descending sequence gives ascending in O(k). Sorting gives the same result in O(k log k). Worse, sorting is unstable for equal elements — it changes the relative order of duplicates, which breaks the lexicographic enumeration. Reversing is both faster and correct for duplicates.
How does the algorithm handle duplicate elements?
The algorithm uses strict comparisons: arr[pivot] < arr[pivot+1] (not <=) and arr[successor] > arr[pivot] (not >=). This ensures that equal elements are treated correctly — the pivot is the rightmost position where a strictly-smaller element precedes a strictly-larger one. Non-strict comparisons skip valid pivots when equal elements are adjacent.
What is the difference between next_permutation and generating all permutations recursively?
Next_permutation computes one permutation at a time in O(n) time and O(1) space. Recursive generation produces all permutations at once in O(n! n) time and O(n! n) memory. Next_permutation is preferred for on-demand enumeration, large n, or memory-constrained environments.
How do you detect when the enumeration has wrapped around?
After calling next_permutation, compare the result to the sorted array. If they match, the enumeration has wrapped around. Alternatively, use hasNextPermutation to check before calling next — it scans for any i where arr[i] < arr[i+1].
What is the k-th permutation problem?
Given n elements and an index k (0-based), find the k-th permutation in lexicographic order directly, without enumerating. This uses the factorial number system: at each position, divide k by (n-1-i)! to determine which element goes there. O(n) time. Different from next_permutation, which finds the immediately-next one.
That's Arrays & Strings. Mark it forged?
3 min read · try the examples if you haven't