Next Permutation

The reliable way to solve Next Permutation is to stop thinking in four memorized steps. Read the suffix, identify where it is already maximal, then make the smallest possible change that moves the whole array forward.

Start With the Mutation Contract

The function receives an integer array and must mutate that same array in place.

The target is:

• the immediately next lexicographically greater arrangement, if one exists;
• otherwise, the lowest lexicographic arrangement.

For example:

[1, 2, 3] -> [1, 3, 2]
[2, 3, 1] -> [3, 1, 2]
[3, 2, 1] -> [1, 2, 3]

The last example wraps around because [3, 2, 1] is already the greatest arrangement of those values.

The memory constraint matters. A solution that generates permutations, copies the array, or creates a sorted temporary suffix may produce the right values but still violate the contract. The intended design uses only a few indices and swaps.

Repeated values are allowed, so the comparison operators must be strict in the right places:

• the pivot condition is nums[i] < nums[i + 1];
• the successor condition is nums[j] > nums[pivot].

Those details determine whether duplicate values are handled correctly.

The central objective is lexicographic adjacency:

1. preserve the longest possible prefix;
2. increase the rightmost position that can increase;
3. make the remaining suffix as small as possible.

That is the entire Next Permutation solution in one sentence. The rest is proving how to implement it.

Find the Suffix That Cannot Grow

Scan from right to left and find the first index i such that:

nums[i] < nums[i + 1]

Call i the pivot.

Everything after i is a non-increasing suffix:

nums[i + 1] >= nums[i + 2] >= ... >= nums[n - 1]

For example:

[1, 3, 5, 4, 2]
       ^  ^  ^
       pivot? 

Scanning from the right:

• 4 < 2 is false;
• 5 < 4 is false;
• 3 < 5 is true.

So the pivot is the 3, and the suffix is [5, 4, 2].

That suffix is already the largest possible ordering of its own values. Rearranging only [5, 4, 2] cannot make the full array larger. There is no larger permutation of those three values than [5, 4, 2].

This is the recognition signal:

A non-increasing suffix is a locked region. To advance the permutation, the change must carry into the element immediately before it.

If no pivot exists, the whole array is non-increasing. The current arrangement is globally maximal, so reverse the entire array:

[3, 2, 1] -> [1, 2, 3]
[3, 2, 2, 1] -> [1, 2, 2, 3]

Why scan from the right? Because lexicographic order gives priority to earlier positions. Changing an earlier element creates a larger jump than changing a later one. The right-to-left scan finds the rightmost position that can still increase, preserving the longest possible prefix.

Turn the Goal Into Three Obligations

Once the pivot is identified, the algorithm has three precise obligations.

1. Increase the rightmost feasible position

The pivot is the rightmost position that can be increased while leaving the prefix before it unchanged.

For:

[1, 3, 5, 4, 2]

the prefix [1] must remain fixed. The 3 is the first position from the right that can move upward.

Changing the 1 instead would also create a larger permutation, but it would skip valid arrangements. The next permutation must make the smallest possible positional change.

2. Choose the smallest valid successor

The replacement must be greater than nums[pivot], but as small as possible.

In the example, the suffix is [5, 4, 2] and the pivot value is 3. The valid successors are 4 and 5. Choose 4.

Because the suffix is non-increasing, scanning from the end and stopping at the first value greater than the pivot finds that smallest valid successor:

[5, 4, 2]
       ^ first value from the right greater than 3: 4

This remains correct with duplicates. The comparison must be strict: an equal value does not increase the permutation.

3. Minimize the suffix

After swapping the pivot and successor, the prefix is now as small as possible while still being larger than the original prefix. The suffix must then be placed in ascending order.

For the running example:

Before swap:  [1, 3, 5, 4, 2]
After swap:   [1, 4, 5, 3, 2]
Final result:  [1, 4, 2, 3, 5]

The state is small and explicit:

• pivot: the index that must increase;
• successor: the index of the smallest suffix value greater than the pivot;
• left and right: the two pointers used for the final reversal.

Naming those obligations makes the implementation easier to debug. If the result is wrong, inspect the state in that order: pivot, successor, suffix boundary.

Why Swap Then Reverse Works

The proof has three parts.

First, no permutation that changes only the suffix can be larger than the current array. The suffix is non-increasing, so it is already the maximum arrangement of those values.

Second, the pivot is the rightmost position that can increase. Every position after it belongs to the maximal suffix. Moving farther left would change the array earlier than necessary and skip over valid permutations.

Third, the successor is the smallest value greater than the pivot. That creates the smallest possible increase at the first changed position.

After the swap, the suffix can be reversed instead of sorted. Before the swap, the suffix is non-increasing. The chosen successor is the rightmost value greater than the pivot, so the remaining suffix keeps enough non-increasing structure that reversal produces non-decreasing order.

The result has:

• the longest unchanged prefix;
• the smallest possible increase at the pivot;
• the smallest possible completion after the pivot.

Therefore, no permutation lies lexicographically between the original array and the result.

A full trace makes the state change visible:

Input:        [1, 3, 5, 4, 2]

Suffix scan:
              5 >= 4 >= 2
Pivot:        index 1, value 3

Successor scan from right:
              2 is not > 3
              4 is > 3
Successor:    index 3, value 4

Swap:
              [1, 4, 5, 3, 2]

Reverse suffix from index 2:
              [1, 4, 2, 3, 5]

The important boundary is pivot + 1. The pivot has already been placed. Reversing from pivot would undo the increase and produce the wrong permutation.

Invariant: Before the final reversal, the prefix through the pivot is already the smallest prefix that is greater than the original prefix. The only remaining job is to produce the smallest suffix completion.

Reject the Brute-Force Baseline

The obvious baseline is:

1. generate permutations;
2. order them lexicographically;
3. find the current arrangement;
4. return the next one.

That approach is useful as a tiny-input oracle when testing an optimized implementation. It is not the submitted algorithm.

The number of permutations grows factorially in the worst case. It also requires materializing many arrangements or maintaining additional ordering state. Even if the input length is modest, the approach ignores the structure that makes this problem cheap.

The optimized plan performs only local work:

1. find the pivot;
2. reverse the whole array if no pivot exists;
3. find the successor;
4. swap;
5. reverse the suffix.

The leverage comes from recognizing the maximal suffix. We do not search the permutation space. We inspect the boundary where the current arrangement runs out of room.

Implement the In-Place Algorithm in Python

The following implementation mutates nums and returns None. It avoids slicing because expressions such as nums[pivot + 1:] allocate a new list.

def next_permutation(nums: list[int]) -> None:
    n = len(nums)

    # Find the rightmost pivot where the sequence can increase.
    pivot = -1
    for i in range(n - 2, -1, -1):
        if nums[i] < nums[i + 1]:
            pivot = i
            break

    # No pivot means the entire array is non-increasing.
    # It is already the greatest permutation.
    if pivot == -1:
        left, right = 0, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        return

    # Find the rightmost value greater than the pivot.
    successor = n - 1
    while nums[successor] <= nums[pivot]:
        successor -= 1

    nums[pivot], nums[successor] = nums[successor], nums[pivot]

    # Reverse the suffix in place.
    left, right = pivot + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Each loop maps directly to one obligation:

• the first loop locates the rightmost feasible increase;
• the second locates the smallest valid successor by scanning the ordered suffix from the right;
• the final loop performs the in-place array reversal needed to minimize the suffix.

The while nums[successor] <= nums[pivot] condition is also a useful defensive detail. The successor must be strictly greater. Equal values do not advance the lexicographic order.

For an input such as [1, 2, 3]:

pivot = 1, value 2
successor = 2, value 3
swap       -> [1, 3, 2]
reverse    -> suffix has one element

For [3, 2, 1], no pivot is found, so the function reverses the entire list and returns.

Dry-Run the Moving State

Use small traces to verify pointer movement before trusting the code.

Shortest nontrivial case

Input: [1, 2, 3]

The first ascending pair from the right is 2 < 3, so:

pivot = 1
successor = 2
swap -> [1, 3, 2]
reverse indices 2 through 2

Result:

[1, 3, 2]

A longer suffix

Input: [1, 3, 5, 4, 2]

The suffix [5, 4, 2] is non-increasing. The pivot is 3.

The first value greater than 3 when scanning from the right is 4:

[1, 3, 5, 4, 2]
       swap 3 and 4
[1, 4, 5, 3, 2]

Now reverse only the suffix beginning at pivot + 1:

[1, 4, 2, 3, 5]

Do not reverse from the pivot. That would turn the increased value back into part of the suffix and break the construction.

Duplicates

Consider:

[2, 2, 1, 2]

The pivot is the 1 at index 2. The successor is the final 2.

swap -> [2, 2, 2, 1]
reverse the one-element suffix

Result:

[2, 2, 2, 1]

The strict comparisons allow the duplicate 2s to remain interchangeable without falsely treating an equal value as an increase.

Audit Cost and Edge Cases

The time complexity is O(n):

• pivot search scans at most the array once;
• successor search scans part of the suffix;
• reversal scans at most half the suffix.

These are sequential passes, so their total remains linear. The extra space is O(1) because the implementation stores only indices and temporary scalar values for swaps.

Audit the implementation against these cases:

Input	Expected result	What it checks
[1]	[1]	length-one boundary
[1, 2, 3]	[1, 3, 2]	ordinary pivot and swap
[3, 2, 1]	[1, 2, 3]	no-pivot wraparound
[3, 2, 2, 1]	[1, 2, 2, 3]	descending duplicate plateau
[1, 1, 5]	[1, 5, 1]	duplicate handling
[1, 5, 1]	[5, 1, 1]	pivot near the front
[2, 2, 1, 2]	[2, 2, 2, 1]	equal successor values
[1, 3, 5, 4, 2]	[1, 4, 2, 3, 5]	suffix reversal boundary

Also verify the mutation contract directly:

nums = [1, 2, 3]
same_object = nums

next_permutation(nums)

assert nums is same_object
assert nums == [1, 3, 2]

Inspect the code for accidental copies:

• no list slicing;
• no sorted(...);
• no auxiliary list or set;
• no generated permutation collection.

For local validation, a brute-force generator can compare results on tiny arrays, including arrays with duplicates. That is a testing tool, not a production strategy. The production algorithm should remain linear and constant-space.

The transferable rule is simple:

When a sequence must advance by the smallest possible amount, find the longest suffix already at its maximum, increase the rightmost boundary that can move, then minimize everything after it.

In a new problem, ask three questions:

1. Which suffix or state region is already locally maximal?
2. What is the rightmost boundary that can still advance?
3. After that boundary moves, what invariant lets you repair the remainder cheaply?

That is the durable pattern behind Next Permutation: read the state, find the locked region, move the boundary, and restore the cheapest valid suffix.