LeetCode 31 – Next Permutation: Problem, Analysis, and Code

Problem description: Given an integer array nums , rearrange it to the next greater permutation in lexicographic order. If such arrangement does not exist, transform the array into the lowest possible order (sorted ascending).

Difficulty: Medium.

Examples:

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

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

Constraints: 1 ≤ nums.length ≤ 100 , 0 ≤ nums[i] ≤ 100 . The algorithm must modify the array in‑place using only O(1) extra space.

Analysis: Scan the array from right to left to find the first index left where nums[left] < nums[left+1] (the first decreasing pair). Then, again from the right, locate the first element larger than nums[left] , swap them, and finally reverse the suffix starting at left+1 to obtain the smallest greater permutation.

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 left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = 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:])