Next Permutation

Rearrange numbers into the next lexicographically larger permutation, in place. Find the rightmost index i with nums[i] < nums[i+1] (the pivot). Swap it with the smallest larger value to its right, then reverse the suffix after i to make it as small as possible.

Traced input: nums = [1, 3, 5, 4, 2] → [1, 4, 2, 3, 5]. Original problem: neetcode.io/problems/next-permutation

Complexity

At most two scans and one reversal.

Key idea

• The suffix after the pivot is non-increasing: it's already the largest arrangement of those numbers.
• To get the next permutation, bump the pivot up by the smallest possible amount.
• The suffix stays non-increasing after the swap, so reversing makes it ascending (smallest).
• No pivot means the array is the last permutation: reverse it all.

Common mistakes

• Swapping with the first larger element instead of the rightmost (smallest) larger one.
• Sorting the suffix instead of reversing it: correct but O(n log n).
• Using > instead of >= when scanning for the pivot, which breaks with duplicates.

Solution

void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    reverse(nums, i + 1, nums.length - 1);
}

void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

void reverse(int[] a, int l, int r) { while (l < r) swap(a, l++, r--); }

def nextPermutation(nums: List[int]) -> None:
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]: i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]: j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])

void nextPermutation(vector<int>& nums) {
    int i = (int)nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = (int)nums.size() - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}

Edge cases

Each one has its own trace in the interactive view.