intermediate10 min read·Updated October 9, 2026

Next Permutation Explained: Finding the Next State of [1, 3, 2]

Master the next permutation algorithm with a step-by-step walkthrough of [1, 3, 2] and [3, 2, 1]. Build a mental model of lexicographic order.

By Learnisim AI·Published October 9, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic array indexing and swapping
  • Understanding of lexicographic (dictionary) order
Next Permutation: In-Place Lexicographic Rearrangement Pivot-and-Reverse Mechanics for [1, 3, 2] and [3, 2, 1] Case 1: Standard Successor [1, 3, 2] 1 i-1 3 pivot 2 end Next Lexicographic [2, 1, 3] 1. Find Pivot: nums[i-1] < nums[i] (1 < 3 at idx 0) 2. Find Successor > pivot from right (swap 1 and 2) 3. Reverse suffix after pivot -> [2, 1, 3] Case 2: Last Permutation Wrap-Around [3, 2, 1] 3 2 1 Strictly Descending (No Pivot) Wrap-Around Reset [1, 2, 3] 1. Scan from right: entirely descending order 2. No valid pivot found (already max permutation) 3. Reverse entire array -> [1, 2, 3] (First element) The 3-Step In-Place Algorithm Pipeline 1. Find the Pivot Scan backwards to find first element smaller than its neighbor nums[i-1] < nums[i] 2. Find Successor & Swap Scan backwards again for smallest element greater than pivot Swap(nums[i-1], nums[j]) 3. Reverse Suffix Reverse all elements directly after pivot to minimize order O(N) time, O(1) space
Next permutation of [1, 3, 2] and of [3, 2, 1] overview diagram
Why

Why We Need a Systematic Way to Find the Next Permutation

Phase 1: The Combinatorial Ordering Wall

Imagine you are handed the sequence nums = [1, 3, 2] and asked to write down all possible arrangements in strictly increasing lexicographic order. You quickly write [1, 2, 3], then [1, 3, 2]. But what comes immediately after [1, 3, 2]? Without a structured rule, you might guess [2, 1, 3]—which is correct—or you might mistakenly try to swap the 3 and 2 and get stuck in an endless loop of unverified permutations.
Now consider the opposite extreme: nums = [3, 2, 1]. When you reach the absolute final permutation of a set, what is the next step? There are no larger arrangements left to form, so standard algorithms must wrap around to the very beginning, returning [1, 2, 3].
If you try to solve this by generating all permutations in memory and sorting them, your program will grind to a halt the moment grows past 12 ( is nearly 500 million entries). We need a way to look at a single array in-place, decide if it can grow larger, and transform it into its immediate successor without extra allocation.
Why We Need a Systematic Next Permutation Algorithm Finding the exact lexicographic successor in-place without generating O(n!) combinations Example 1: The Lexicographic Successor 1 3 2 nums = [1, 3, 2] Systematic Scan 2 1 3 Successor: [2, 1, 3] Example 2: The Last Permutation Wrap 3 2 1 nums = [3, 2, 1] Max reached (no larger) 1 2 3 Wraps to: [1, 2, 3] Why Brute-Force Generation Fails & The In-Place Solution The Combinatorial Wall • Generating all O(n!) permutations in memory • Grinds to a halt when n grows past 12 • n=12 is nearly 500 million entries Result: Out of memory / Time Limit Exceeded Systematic 3-Step Scan 1. Find pivot: first A[i] < A[i+1] from right 2. Find successor: smallest A[j] > A[i] 3. Swap & reverse suffix in-place Guarantees exact immediate lexicographic jump Complexity & In-Place • Time Complexity: O(n) scan & reverse • Space Complexity: O(1) extra allocation • Handles descending wrap-around cleanly Standard library standard (e.g. std::next_permutation)
Why We Need a Systematic Way to Find the Next Permutation diagram
Model

Deconstructing Lexicographic Order: The Mechanics Behind Rearranging Elements

Phase 2: The Core Mental Model

To understand how to get from [1, 3, 2] to the next lexicographic permutation, we need to stop thinking about arrays as mere collections and start looking at them as numbers read from left to right. Just like decimal numbers where altering the tens place changes the value far more than altering the ones place, in a permutation, changing an element earlier in the array has a massive impact on the overall sequence value.
When we look at our locked starting sequence [1, 3, 2], the most significant digits are on the left. The 1 at index 0 fixes the prefix, while the suffix [3, 2] is already descending—meaning it has reached the highest possible value for those specific positions. To find the next immediate permutation, we cannot make any more changes within that descending suffix; we must look to the left to find a place where we can increase a number by the smallest possible margin.

The Anatomy of a Suffix

Consider how the suffix [3, 2] behaves:
•It is strictly decreasing from left to right.
•Any rearrangement of a strictly decreasing suffix only yields smaller permutations, not larger ones.
•Therefore, to advance to the next permutation, our first operational step is always scanning from the right to find the boundary where this descending order breaks.
In our working example [1, 3, 2], the break occurs at index 0 (1 is less than 3). If we instead had our second locked example [3, 2, 1], the entire array is a descending suffix, which signals that we have hit the absolute end of the permutation cycle and must wrap around to the beginning.
python
# Examine the suffix of [1, 3, 2]
# Is [3, 2] increasing or decreasing?
# Where does the non-increasing sequence break when scanning from right to left?
Deconstructing Lexicographic Order: Next Permutation of [1, 3, 2] Phase 1: Scan Find first decreasing element 1 idx 0 3 Pivot? 2 Suffix Scan Right to Left nums[0] < nums[1] (1 < 3) → Pivot found at index 0! Phase 2: Swap Just larger than pivot 1 Pivot 3 Suffix max 2 Element Swap 1 & 2 Array becomes: [2, 3, 1] Phase 3: Reverse Suffix Minimizes the suffix to get the immediate next permutation 2 New Prefix 1 Reversed 3 Reversed Resulting Next Permutation: [2, 1, 3] For [3, 2, 1] (fully descending), no pivot exists → wraps to [1, 2, 3] Key Rule: Descending suffix [3, 2] is already at maximum value. Increment prefix element, then reverse suffix for smallest increase.
Deconstructing Lexicographic Order: The Mechanics Behind Rearranging Elements diagram
Worked example

Tracing the Algorithm: Step-by-Step Execution on [1, 3, 2]

Phase 3: Worked Example

To see our lexicographic rules in action, let us trace the algorithm end-to-end using our working array nums = [1, 3, 2]. We will observe every intermediate state, pointer movement, and array mutation until we hit the exact expected result of [2, 1, 3].
Given the array nums = [1, 3, 2]:
Step 1: Find the first decreasing element from the right.
We scan backwards from the end of the array to locate the first index i where nums[i] < nums[i + 1].
- Compare indices i = 1 and i = 2: nums[1] is 3, nums[2] is 2. Is 3 < 2? False.
- Compare indices i = 0 and i = 1: nums[0] is 1, nums[1] is 3. Is 1 < 3? True.
- We stop here. Our pivot index is i = 0 (value 1), and the boundary of our descending suffix begins at i + 1 = 1 (value 3).
Step 2: Find the rightmost successor to swap with.
Now we scan backwards again from the very end of the array to find the first element greater than our pivot nums[i] (1).
- Check nums[2] (2): Is 2 > 1? True.
- We stop immediately because this is the rightmost valid swap partner. Our swap index is j = 2 (value 2).
Step 3: Swap the pivot and the successor.
We exchange the values at index 0 and index 2.
- Array before swap: [1, 3, 2]
- Array after swapping nums[0] (1) with nums[2] (2): [2, 3, 1]
Step 4: Reverse the suffix.
Everything to the right of our original pivot index (i = 0) must now be reversed to ensure it is as small as possible (strictly increasing order). The suffix currently starts at index 1 and spans to index 2 ([3, 1]). Reversing [3, 1] gives [1, 3].
- Array after reversing suffix: [2, 1, 3]
Result:
The transformation [1, 3, 2] → [2, 1, 3] is complete, successfully yielding the immediate next lexicographic permutation in-place.
python
def nextPermutation(nums: list[int]) -> None:
    # Step 1: Find pivot
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    
    if i >= 0:
        # Step 2: Find rightmost successor
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        # Step 3: Swap
        nums[i], nums[j] = nums[j], nums[i]
        
    # Step 4: Reverse suffix
    nums[i + 1:] = reversed(nums[i + 1:])
Tracing Next Permutation on [1, 3, 2] Phase 3: Steps 1 to 3 — Pivot Identification, Successor Search, & Swap Step 1: Find Pivot Scan backwards for first nums[i] < nums[i+1] idx 0 1 idx 1 3 idx 2 2 Pivot i=0 (val 1) found! Step 2: Find Successor Scan from right for first > pivot (1) idx 0 1 idx 1 3 idx 2 2 Successor j=2 (val 2) Step 3: Swap Exchange pivot (idx 0) and successor (idx 2) idx 0 2 idx 1 3 idx 2 1 Array after swap: [2, 3, 1]
Tracing the Algorithm: Step-by-Step Execution on [1, 3, 2] diagram
Practice

Applying the Pivot-and-Reverse Mechanics to a New Sequence

Phase 4:

Now that you have seen how [1, 3, 2] transforms into [2, 1, 3] through pivot detection, element swapping, and suffix reversal, it is time to test your mental trace on a closely related input. Consider the array nums = [2, 3, 1]. Following the exact same four-step procedure we established in the previous phase, you will identify where the ascending sequence breaks from the right, locate the necessary swap candidate, perform the exchange, and reverse the remaining tail.
To solve this mentally or on scratchpad, walk through these three checkpoints:
1. Scan from the right to find the first index where nums[i] is strictly less than nums[i+1]. What is the value and index of this pivot?
2. Scan again from the right to find the smallest index where nums[j] is strictly greater than your pivot. What gets swapped?
3.Once the swap is executed, what does the suffix look like before you reverse it, and what is the final lexicographic result?
Take a moment to write down the intermediate array state right after the swap, before applying the reversal step. This is where most off-by-one errors occur in interviews.
Try this: Given nums = [2, 3, 1]:
1.Identify pivot i where nums[i] < nums[i+1].
2.Identify rightmost j where nums[j] > nums[i].
3.Swap nums[i] and nums[j], then reverse suffix from i+1 to end.

Question: What is the final modified array nums after this complete operation?
Apply

Transferring the Pivot-and-Reverse Pattern to Sequence Wrap-Arounds

Phase 5: Transfer

Now that you have mastered the four-step mechanics on [1, 3, 2] and verified your intuition on [2, 3, 1], let us push the algorithm to its ultimate boundary: a strictly descending sequence like [3, 2, 1]. Recall that our original exploration promised a transition from our base example to this maximum lexicographic state. When you apply the standard pivot-finding rule () scanning from right to left on [3, 2, 1], every adjacent pair is non-increasing (). No pivot exists.
Instead of failing, the algorithm's mechanical consequence is profound: because no pivot can be found, the entire array is treated as a single descending suffix. Step 4—reversing the entire sequence—transforms [3, 2, 1] straight into [1, 2, 3]. This wrap-around behavior is not a special case branch in your code; it is the natural mathematical fallout of the reverse step when the structural peak of the permutation space is reached. You can now use this exact zero-pivot signature to detect when any combinatorial generator has completed a full cycle.
python
def nextPermutation(nums: list[int]) -> None:
    # Find the largest index i such that nums[i] < nums[i + 1]
    # If no such index exists, the permutation is the last permutation
    pass

FAQ

What is the next permutation of [1, 3, 2]?
The next permutation of [1, 3, 2] is [2, 1, 3]. This is found by identifying the pivot 1, finding the smallest element greater than 1 to its right (which is 2), swapping them, and reversing the suffix.
What happens when you find the next permutation of the last possible sequence, like [3, 2, 1]?
When the sequence is strictly decreasing, it is already the last lexicographical permutation. The algorithm wraps around to the beginning, returning the lowest possible order: [1, 2, 3].
What is the time and space complexity of the next permutation algorithm?
The algorithm runs in O(N) time because it requires at most two passes through the array (one to find the pivot and one to reverse the suffix). It uses O(1) auxiliary space since all rearrangements are done in place.
Why do we reverse the suffix after swapping the pivot?
After swapping the pivot with the next largest element, the suffix to the right of the pivot is still in descending order. Reversing it ensures it becomes the smallest possible lexicographical order, maintaining the strictly increasing sequence required for the 'next' immediate permutation.

Keep learning