Next Permutation | One Hint Away

Problem: LeetCode 31 · Next Permutation (Medium, free)

Rearrange the array into the next bigger order (lexicographically), in place, with constant extra memory. If it is already the biggest order, wrap around to the smallest.

Example: [1, 3, 5, 4, 2] → [1, 4, 2, 3, 5]. Edge case: [3, 2, 1] → [1, 2, 3].

The idea

Pivot: walk in from the right while the values climb. The first value that drops (nums[i] < nums[i + 1]) is the pivot. Everything to its right is a falling tail, already in its biggest order.
Partner: from the right, the first value bigger than the pivot. Because the tail falls, this is the smallest value in the tail that is still bigger. Swap them.
Reset: the tail still falls after the swap, so reverse it to make it climb (its smallest order).
No pivot means the whole array falls: reversing it gives the smallest order.

Pseudocode

Pseudocode · any language

function nextPermutation(nums):
    n = length(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i = i - 1                // walk left
    if i >= 0:                   // pivot found
        j = n - 1
        while nums[j] <= nums[i]:
            j = j - 1
        swap nums[i], nums[j]
    reverse nums from i + 1 to n - 1

The trap: stopping after the swap. The tail still falls, so it is in its biggest order. On [1, 3, 5, 4, 2] the swap gives [1, 4, 5, 3, 2], which is bigger but not the next one; reversing the tail gives the right answer, [1, 4, 2, 3, 5].

Code

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

    static void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left = left + 1;
            right = right - 1;
        }
    }

    static void swap(int[] nums, int a, int b) {
        int t = nums[a]; nums[a] = nums[b]; nums[b] = t;
    }
}

def next_permutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i = i - 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j = j - 1
        nums[i], nums[j] = nums[j], nums[i]
    reverse(nums, i + 1, n - 1)

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

#include <bits/stdc++.h>
using namespace std;

void reverseRange(vector<int>& nums, int left, int right) {
    while (left < right) {
        swap(nums[left], nums[right]);
        left = left + 1;
        right = right - 1;
    }
}

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

function nextPermutation(nums) {
    const n = nums.length;
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i = i - 1;
    }
    if (i >= 0) {
        let j = n - 1;
        while (nums[j] <= nums[i]) {
            j = j - 1;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    reverse(nums, i + 1, n - 1);
}

function reverse(nums, left, right) {
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left = left + 1;
        right = right - 1;
    }
}

Complexity

Time: O(n). The pivot scan, the partner scan and the reverse each walk the array at most once.
Space: O(1). Only swaps inside the array.

How it was tested

All four versions were compared against a brute force (list every distinct order with itertools.permutations, sort, take the next one, wrapping at the end) on 1,515 cases: edge cases (single element, two elements, all equal, sorted, reversed, duplicates) plus 1,500 random arrays of length 1 to 7. All four agreed with the brute force on every case, and with each other on 50 random arrays of length 100 (LeetCode's maximum). Re-run on 31 October 2026 on 3,006 more cases (3,000 random arrays of length 1 to 7 with repeats, plus the example, [3, 2, 1], [1, 2, 3], [1, 1, 5], [1] and [1, 5, 1]): all four matched the brute force on every one.

The idea

Pseudocode

Code

Complexity

How it was tested

Practice