31. Next Permutation

[mengyushi]

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        '''

        In-Place, Constant extra memory
                i
        1 5 8 4 7 6 5 3 1
                |-> sorted reversly, no permulation can make it larger
              |-> possible permulation make it larger
                  change with smallest possile larger num
                  and sort the following (or just reverse it is fine)

        1).find first decreasing # from tail

        1,3,4,5,6,7,4 4 is the first decreasing #

        2). switch it with # JUST larger than it => is 5

        1 5 8 5 7 6 4 3 1
                |-> sorted reversely

        3). reverse (sort) remained tail numbers

        1 5 8 5 1 3 4 6 7 DONE

        * Special Case when already the largest or decreased at 0
            i
            5 4 3 2 1  =>. 1 2 3 4 5 

            Just reverse everything

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

        '''

        # 1).find first decreasing # from tail
        N = len(nums)
        i = N-1
        while i and nums[i-1]>=nums[i]:
            i-=1

        if not i:
            nums.reverse()
        else:
            nums[i:] = nums[i:][::-1]
            j = bisect.bisect(nums,nums[i-1],i) # searching from ith
            nums[i-1], nums[j] = nums[j], nums[i-1]