31. Next Permutation

Solution 1: Two Pointer

class Solution:
    """
    Do not return anything, modify nums in-place instead.
    """
    def nextPermutation(self, nums: List[int]) -> None:
        idxOf1stNonIncreNum, idxOfSwapTgt = 0, 0
        
        n = len(nums)
        for idxI in range(n-2, -1, -1):
            if nums[idxI+1] >= nums[idxI]:
                idxOf1stNonIncreNum = idxI
                 
                for idxJ in range(n-1, idxOf1stNonIncreNum-1, -1):
                     if nums[idxJ] > nums[idxOf1stNonIncreNum]:
                        idxOfSwapTgt = idxJ
                        break
                
                # The idxOfSwapTgt is on the right of idxOf1stNonIncreNum
                if  idxOf1stNonIncreNum < idxOfSwapTgt:
                    nums[idxOf1stNonIncreNum], nums[idxOfSwapTgt] = nums[idxOfSwapTgt], nums[idxOf1stNonIncreNum]
                    nums[idxOf1stNonIncreNum + 1: ] = sorted(nums[idxOf1stNonIncreNum + 1: ])
                    return nums
        nums.sort()
        return nums

Time Complexity: O(N^2)
Space Complexity: O(1)

Reference

https://www.cnblogs.com/grandyang/p/4428207.html
https://medium.com/@ChYuan/leetcode-no-31-132-pattern-%E5%BF%83%E5%BE%97-medium-e02ecf53817f