LeetCode 31. Next Permutation

Description

https://leetcode.com/problems/next-permutation/

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 (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Explanation

1. find first decreasing element
2. find number just larger than first decreasing element and swap with the first decreasing element
3. sort all elements after the first decrease element position

Python Solution

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        # find first decreasing element
        i = len(nums) - 2
        while i > -1:
            if nums[i] < nums[i + 1]:                
                break
            i -= 1
            
        # find number just larger than first decreasing element
        j = i
        min_large = sys.maxsize
        for k in range(i, len(nums)):
            
            if nums[k] > nums[i]:
                min(min_large, nums[k]) 
                j = k
                
        # swap
        temp = nums[j]
        nums[j] = nums[i]
        nums[i] = temp
                
        # sort all elements after the first decrease element position
        nums[i + 1:] = sorted(nums[i + 1:])
        
    
            
            

• Time Complexity: ~N
• Space Complexity: ~1