Next Permutation

"""
Intuition:
To get the next lexicographically greater permutation, we want to make the smallest possible increase.
Scan from right to find the first index (pivot) where nums[i] < nums[i+1]. This is the first place
where we can increase the number. Then, from the right side, find the smallest element greater than
nums[i] and swap it with the pivot. Finally, reverse the suffix (i+1 to end) to make it the smallest
possible order. If no pivot exists (array is fully non-increasing), reverse the whole array to get
the smallest permutation.

Trick: if the array is already sorted in decreasing order,then reverse the array to get the smallest number possible.
"""


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        #find pivot element first
        i=len(nums)-2
        while i>=0 and nums[i]>=nums[i+1]:
            i-=1
        #pivot=i,now find the just bigger element than the pivot in the right side of the array and right side is already increasing order
        if i<0:
            nums.reverse()
            return

        j=len(nums)-1
        if i>=0:
            while j>i and nums[j]<=nums[i]:
                j-=1
            nums[j],nums[i]=nums[i],nums[j]
        nums[i+1:]=reversed(nums[i+1:])