Next Permutation — Editorial

Opening the reading…

Intuitionwhy the suffix can be rearranged independently

A permutation becomes larger at the first position where it differs from the old one. To get the immediate next permutation, you therefore want to keep the longest possible prefix unchanged and increase the rightmost position that can still be increased. Any change farther left would skip over valid permutations and produce an answer that is too large.

Scan from the right until the descending suffix ends. The first index i with nums[i] < nums[i + 1] is the position to increase. Everything after i is already in non-increasing order, so it contains no larger arrangement with the same prefix. Find the smallest value in that suffix that is larger than nums[i], swap it with nums[i], and reverse the suffix. Reversing makes that suffix ascending, which is its smallest possible order.

The pivot creates the smallest possible increase, and the reversed suffix removes all unnecessary extra size.

Approach

Start i at n - 2 and move left while nums[i] >= nums[i + 1], because this identifies the longest non-increasing suffix and skips positions that cannot be increased without changing an earlier prefix.

If i is still valid, scan j from the last index left while nums[j] <= nums[i], because the suffix is non-increasing and the first value you meet that is larger than the pivot is the smallest valid successor.

Swap nums[i] and nums[j], because this increases the permutation at the rightmost possible position while leaving every earlier value unchanged.

Reverse the range from i + 1 to the end, because the suffix was descending before the swap and its ascending arrangement is the smallest order available after the prefix has increased.

If no pivot exists, i is -1 and the same reverse operation covers the entire array, turning a completely descending permutation into the smallest ascending permutation without needing a separate case.

Complexitythe array is scanned and rearranged in place

MEASURE	BOUND	WHY
Time	O(n)	The pivot scan, successor scan, and reversal each move only across array positions. They are sequential operations rather than nested scans, so each position is examined or swapped a constant number of times.
Space	O(1) extra	The algorithm stores only indices and uses constant-size temporary storage for swaps. The result remains in nums, so output storage is not counted; the bound stays O(1) for every input shape, including an entirely descending array.

Here n is the number of elements in nums.

Annotated solutionC++ · in-place two-pointer scan and reversal

CPPFind the pivot, swap it with its smallest larger successor, then reverse the suffix in place.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 2;

        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }

        if (i >= 0) {
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                --j;
            }
            swap(nums[i], nums[j]);
        }

        reverse(nums.begin() + i + 1, nums.end());
    }
};

The final reverse is deliberately outside the if block. When a pivot exists, it minimizes the suffix after the increase. When no pivot exists, i is -1, so nums.begin() + i + 1 is the beginning of the array and the entire descending array is reversed. One operation handles both the ordinary and wraparound cases.