10 lines Python solution - 59ms

  • 0

    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]
    elif i==1:

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.