LeetCode 31 – Next Permutation: Problem Explanation and Multi‑Language Solutions

LeetCode problem 31 "Next Permutation" asks to rearrange a numeric array into the lexicographically next greater permutation, modifying the array in‑place using only constant extra space. If such a permutation does not exist, the array should be transformed into the smallest (sorted ascending) order.

Examples:

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

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

Key observations: scanning from the end, find the first index where nums[i] < nums[i+1] (the first decreasing pair). Then find the smallest element larger than nums[i] to its right, swap them, and finally reverse the suffix starting at i+1 to obtain the minimal greater arrangement.

Java implementation:

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

C++ implementation:

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

Python implementation:

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