Next Permutation [Medium] — In-Place Rearrangement

Problem Statement

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of its digits.

If no such arrangement is possible (already the largest), rearrange it as the lowest possible (ascending) order.

Must be done in-place with O(1) extra memory.

Example:

Input:  [1,2,3] → Output: [1,3,2]
Input:  [3,2,1] → Output: [1,2,3]
Input:  [1,1,5] → Output: [1,5,1]

Intuition

Three steps:

Scan right→left to find first index i where nums[i] < nums[i+1]
Scan right→left to find first index j where nums[j] > nums[i], then swap
Reverse the suffix [i+1 … end]

Solutions

C

void reverse(int* nums, int l, int r) {
    while (l < r) { int t = nums[l]; nums[l++] = nums[r]; nums[r--] = t; }
}
void nextPermutation(int* nums, int n) {
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i+1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
    reverse(nums, i + 1, n - 1);
}

C++

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

Java

public void nextPermutation(int[] nums) {
    int n = nums.length, i = n - 2;
    while (i >= 0 && nums[i] >= nums[i+1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
    // reverse suffix
    int l = i + 1, r = n - 1;
    while (l < r) { int t = nums[l]; nums[l++] = nums[r]; nums[r--] = t; }
}

JavaScript

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

Python

def nextPermutation(nums: list[int]) -> None:
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # reverse suffix
    nums[i+1:] = nums[i+1:][::-1]

Complexity

Time: O(n) — at most two scans
Space: O(1) — in-place

Follow-ups

Previous Permutation with same trick
All permutations via backtracking