Next Permutation

31.Next Permutation

Array

Two Pointers

Math

Problem Statement:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

Example:

Input:

nums = [1,2,3]

→

Output:

[1,3,2]

Algorithm:

1. Find first decreasing element from right
2. Find smallest larger number to its right
3. Swap these two numbers
4. Reverse all numbers to the right

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    
    // Find first decreasing element from right
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = nums.length - 1;
        // Find smallest larger number to right
        while (j >= 0 && nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    
    // Reverse remaining right portion
    reverse(nums, i + 1, nums.length - 1);
}

public void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

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

Python Solution:

def nextPermutation(self, nums: List[int]) -> None:
    i = len(nums) - 2
    
    # Find first decreasing element
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
        
    if i >= 0:
        j = len(nums) - 1
        # Find smallest larger number
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    
    # Reverse the remaining portion
    left = i + 1
    right = len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

C++ Solution:

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        
        // Find first decreasing element
        while(i >= 0 && nums[i] >= nums[i + 1]) i--;
        
        if(i >= 0) {
            int j = nums.size() - 1;
            // Find smallest larger number
            while(j >= 0 && nums[j] <= nums[i]) j--;
            swap(nums[i], nums[j]);
        }
        
        // Reverse the remaining portion
        reverse(nums.begin() + i + 1, nums.end());
    }
};