LeetCode 31 – Next Permutation: Problem, Analysis, and Java, C++, Python Solutions

Problem description: Implement a function that rearranges a given integer array into the next lexicographically greater permutation; if such a permutation does not exist, rearrange it into the smallest (ascending) order.

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

Analysis: Scan the array from right to left to locate the first index where nums[i] < nums[i+1] (the first decreasing pair). Then, again from the right, find the first element larger than nums[i], swap these two elements, and finally reverse the sub‑array to the right of index i to obtain the minimal greater permutation.

Java solution:

public void nextPermutation(int[] nums) {
    int left = nums.length - 2;
    // Find first decreasing element from the right
    while (left >= 0 && nums[left] >= nums[left + 1])
        left--;
    // If such element exists, find element just larger than nums[left]
    if (left >= 0) {
        int right = nums.length - 1;
        while (nums[right] <= nums[left])
            right--;
        swap(nums, left, right);
    }
    // Reverse the suffix
    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++ solution:

void nextPermutation(vector<int>& 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 solution:

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:])

Author bio: The article is authored by "Bo Ge" (Wang Yibo), an experienced algorithm enthusiast who has solved over 2,000 problems across multiple platforms and shares practical algorithmic insights.