31. Next Permutation

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # main idea is to (1) find a larger number than current nums (2) increment between next bigger and current number is as small as possible ==> start from lower digit/ least significant digit
        # time O(N) space O(1)
        size = len(nums)
        # step0,  start from last one, looping towards head of nums
        for i in range(size-1,0,-1):
            cur = nums[i]
            pre = nums[i-1]
            # step1 find the smallest number on the right that's lager than pre
            if cur > pre:
                idx = i 
                _min = cur 
                for k in range(i+1,size):
                    if nums[k] > pre and nums[k] <= _min: # note, if using <, for arr[i:] where there are equal numbers at the end will not be sorted by using swap method
                        idx = k 
                        _min = nums[k]
                
                #step2, swap pre with _min
                nums[i-1] = _min
                nums[idx] = pre
                
                
                #step3: sort arr start from curr or  nums[i] in ascending order
                n  = size - i
                for k in range(n//2):
                    nums[i+k],nums[i+n-k-1] =nums[i+n-k-1] ,nums[i+k]
                return 
        #step4 there is not next bigger number(current one is biggest), so reverse it to convert into smallest
        for i in range(size//2):
            nums[i],nums[size-1-i] =  nums[size-1-i],nums[i]