"""

Step1: Travese backward find the first appreance of nums[i-1] < nums[i]

Step2: Sort nums[i:] in ascending order

Step3: Find nums[j] in nums[i:n] that is just larger than nums[i-1], and switch nums[j] with nums[i-1]

Note: if nums in the original list is already in descending order, return the next permutation as nums sorted in ascending order

"""

class Solution(object):

def nextPermutation(self, nums):

for i in range(len(nums)-1,0,-1):

if nums[i] > nums[i-1]:

nums[i:] = sorted(nums[i:])

j = i

while nums[j] <= nums[i-1]:

j += 1

nums[i-1],nums[j] = nums[j],nums[i-1]

break

elif i==1:

nums.reverse()