Next Permutation: The Three-Step Algorithm

Given an array of integers, rearrange it into the lexicographically next greater permutation. If the array is already the largest permutation (fully descending), rearrange it into the smallest (fully ascending). The rearrangement must be done in-place with O(1) extra memory.

This is LeetCode 31: Next Permutation, and it shows up constantly in interviews. The algorithm has three clear steps, and once you see why each step works, it becomes one of those problems you can write from memory in under a minute.

The problem

Given nums = [1, 2, 3], the next permutation is [1, 3, 2]. Given nums = [3, 2, 1], the array is already the largest permutation, so you wrap around to [1, 2, 3]. Given nums = [1, 1, 5], the next permutation is [1, 5, 1].

The key word is lexicographically. Think of it like dictionary order for numbers. You want the smallest rearrangement that is still larger than the current one. If no larger arrangement exists, you produce the smallest one.

The approach

The algorithm has three steps:

1. Find the pivot. Scan from right to left. Find the first index i where nums[i] is less than nums[i + 1]. This is the rightmost position where the sequence is still ascending. Everything to the right of i is in descending order, meaning that suffix is already at its maximum permutation. Index i is the pivot.

2. Find the successor. Scan from right to left again, this time looking for the smallest element in the suffix that is larger than nums[i]. Because the suffix is descending, the first element you find that is greater than nums[i] is the right one. Swap it with nums[i].

3. Reverse the suffix. After the swap, the suffix (everything after index i) is still in descending order. Reverse it to make it ascending. This turns the suffix into the smallest possible arrangement, giving you the next permutation.

If step 1 finds no pivot (the entire array is descending), just reverse the whole array to get the smallest permutation.

The solution

def nextPermutation(nums: list[int]) -> None:
    n = len(nums)
    i = n - 2

    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        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

The first while loop finds the pivot by walking left until nums[i] is less than nums[i + 1]. If i drops below 0, the whole array is descending and there is no pivot.

When a pivot exists, the second while loop finds the successor in the suffix. Since the suffix is descending, scanning from the right and stopping at the first value greater than nums[i] gives the smallest such value. After swapping, the suffix remains descending (the swap does not break the ordering because the successor was chosen to be the smallest element larger than the pivot).

The final while loop reverses the suffix in-place using two pointers. This converts the descending suffix into ascending order, producing the smallest possible tail.

Visual walkthrough

Let's trace through nums = [1, 5, 8, 4, 7, 6, 5, 3, 1] step by step.

After the three steps, the array becomes [1, 5, 8, 5, 1, 3, 4, 6, 7]. That is the lexicographically next permutation. The pivot (4) was replaced by the smallest larger value from the suffix (5), and then the suffix was reversed to its smallest form.

Complexity

Time is O(n). Each of the three steps makes at most one pass over the array. Finding the pivot scans right to left. Finding the successor scans right to left within the suffix. Reversing the suffix uses two pointers that meet in the middle. Total work is at most 2n comparisons and n/2 swaps.

Space is O(1). Everything is done in-place. No extra arrays, no recursion stack. Just a few index variables.

The building blocks

This problem is composed of two reusable bricks that appear across many other problems.

Suffix analysis

Scanning from the right to identify a descending suffix is the core insight. The suffix [7, 6, 5, 3, 1] is already at its maximum permutation. No rearrangement of those elements can produce a larger sequence. That is why you must look to the left of the suffix to make progress. This same idea of analyzing a suffix from the right appears in problems like finding the next greater element and in monotonic stack patterns.

In-place reversal

The two-pointer reverse is the same brick used in Rotate Array. You set left at the start, right at the end, swap them, and walk inward until the pointers meet. No extra space needed.

def reverse(nums: list[int], left: int, right: int) -> None:
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

This micro-pattern appears in string reversal, the triple reverse trick for rotation, and palindrome checking. In Next Permutation, reversing the suffix converts it from descending (maximum) to ascending (minimum), which is exactly what you need to produce the smallest valid tail.

Edge cases

Already the largest permutation. When the array is fully descending like [3, 2, 1], step 1 finds no pivot (i drops to -1). You skip the swap and just reverse the entire array to get [1, 2, 3]. The code handles this naturally because left starts at i + 1 = 0 and right starts at n - 1, so the reverse covers the whole array.

All elements the same. An array like [2, 2, 2] is effectively descending (no index satisfies nums[i] being strictly less than nums[i + 1]). The pivot search fails, and the full reverse produces the same array. This is correct because there is only one unique permutation.

Two elements. For [1, 2], the pivot is at index 0, the successor is at index 1, you swap to get [2, 1], and the suffix (empty) needs no reversal. For [2, 1], there is no pivot, so you reverse to get [1, 2]. Both cases work correctly.

From understanding to recall

You understand the three steps. You can trace through an example. But can you write the solution from scratch in under two minutes?

That is what interviews demand. Under pressure, small details trip people up: using the wrong comparison direction in the pivot search, scanning the suffix left-to-right instead of right-to-left, forgetting to reverse after the swap. These are not conceptual gaps. They are recall problems.

The three-step algorithm for Next Permutation is built from two simple building blocks: suffix analysis and in-place reversal. Each brick is small enough to drill independently. When you can write both from memory, the full solution is just combining them in the right order.

Related posts

• Permutations - Generates all n! permutations using backtracking. Understanding the full permutation space helps you see why Next Permutation produces the lexicographically next one.
• Rotate Array - Uses the same in-place reversal brick. The triple reverse trick is three calls to the same two-pointer reverse that Next Permutation uses as its final step.

CodeBricks breaks Next Permutation into its suffix analysis and in-place reversal building blocks, then drills them independently with spaced repetition. You type each brick from scratch until it is automatic. When the problem shows up in your interview, you do not think about it. You just write it.