Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Next Permutation
• Main tags: Array, Two Pointers

What the problem is really asking

The array represents one permutation of the numbers.

The task is to mutate it into the very next permutation in lexicographic order, which means:

• make the number just a little larger
• keep that increase as small as possible
• do everything in place

If the current permutation is already the largest possible one, such as [3, 2, 1], then there is no larger answer. In that case, the correct result is the smallest permutation, which is ascending order.

So this is really a “find the next larger arrangement with the smallest possible change” problem.

The key insight

The right side of the array changes fastest in lexicographic order.

That means the next permutation should keep as much of the left side unchanged as possible, and only adjust the array near the end.

Look from right to left for the first index where the numbers stop decreasing:

nums[pivot] < nums[pivot + 1]

That index is the pivot. It is the first place where a slightly larger permutation is still possible.

Everything to the right of that pivot must already be in non-increasing order. If it were not, a larger permutation could have been formed without touching the pivot, which would contradict choosing the first such place from the right.

Once that pivot is found:

1. swap it with the smallest number to its right that is still larger than it
2. reverse the suffix to make that suffix as small as possible

That gives the next permutation, not just some larger permutation.

How to derive the optimal solution

Start from the brute-force idea:

• generate all permutations
• sort them
• find the current one
• take the next one

That is obviously too expensive.

A better way is to reason directly about lexicographic order.

Suppose the array is:

[1, 2, 7, 4, 3, 1]

Reading from the right:

• 4, 3, 1 is decreasing
• 7, 4, 3, 1 is still decreasing
• but 2 < 7, so index 1 is the pivot

Why does that matter?

Because the suffix after the pivot is already the largest arrangement of those suffix values. There is no way to make the whole array slightly larger by changing only that suffix.

So the pivot is the first position that must increase.

To increase it by the smallest amount, swap it with the rightmost value greater than it. In this example, swap 2 with 3:

[1, 3, 7, 4, 2, 1]

Now the array is larger, but the suffix is still too large. To get the immediate next permutation, make the suffix as small as possible by reversing it:

[1, 3, 1, 2, 4, 7]

That works because the suffix was in non-increasing order before the swap, so after the swap it is still best normalized by reversing it into ascending order.

This gives:

• Time: O(n)
• Extra space: O(1)

Why reversing the suffix is enough

After the pivot swap, the prefix is already fixed at the smallest larger value.

The only remaining goal is to choose the smallest possible suffix. Since the suffix is in descending order, reversing it turns it into ascending order, which is the minimum arrangement of those remaining numbers.

That is the whole greedy argument:

• change the array as far to the right as possible
• increase that position by the smallest amount possible
• minimize everything after it

Practical way to remember it

This problem is easier to remember as a three-step recipe:

1. scan from the right to find the first increasing pair
2. swap that value with the next larger value on its right
3. reverse everything to the right

If step 1 fails, the whole array is descending, so just reverse the entire array.

Python solution

from typing import List


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Rearrange nums into the next lexicographically greater permutation.
        Modify the input list in place.
        """
        pivot_index = self._find_pivot_index(nums)

        if pivot_index == -1:
            self._reverse_range(nums, start_index=0, end_index=len(nums) - 1)
            return

        swap_index = self._find_rightmost_successor(
            nums=nums,
            pivot_index=pivot_index,
        )
        nums[pivot_index], nums[swap_index] = nums[swap_index], nums[pivot_index]

        # The suffix is in non-increasing order, so reversing it produces the
        # smallest possible suffix for the new prefix.
        self._reverse_range(
            nums,
            start_index=pivot_index + 1,
            end_index=len(nums) - 1,
        )

    def _find_pivot_index(self, nums: List[int]) -> int:
        """Return the rightmost index where nums[i] < nums[i + 1]."""
        for index in range(len(nums) - 2, -1, -1):
            if nums[index] < nums[index + 1]:
                return index
        return -1

    def _find_rightmost_successor(self, nums: List[int], pivot_index: int) -> int:
        """
        Return the rightmost value greater than the pivot.

        Scanning from the end guarantees the smallest larger replacement because
        the suffix is in non-increasing order.
        """
        pivot_value = nums[pivot_index]

        for index in range(len(nums) - 1, pivot_index, -1):
            if nums[index] > pivot_value:
                return index

        raise ValueError("A pivot successor must exist when a pivot exists.")

    def _reverse_range(
        self,
        nums: List[int],
        start_index: int,
        end_index: int,
    ) -> None:
        """Reverse nums[start_index:end_index + 1] in place."""
        while start_index < end_index:
            nums[start_index], nums[end_index] = nums[end_index], nums[start_index]
            start_index += 1
            end_index -= 1