10 lines Python solution + explanation


  • 0
    A
    def nextPermutation(self, nums):
        i, j = len(nums)-2, len(nums)-1
        while i >= 0:
            if nums[i] < nums[i+1]:
                while nums[j] <= nums[i]: j -= 1
                nums[i], nums[j] = nums[j], nums[i]
                break
            i -= 1
        s, e = i+1, len(nums)-1
        while s < e: nums[s], nums[e], s, e = nums[e], nums[s], s+1, e-1
    
    1. From right to left, find the first digit (D1) which violates the increasing property
    2. From right to left, find the first digit (D2) which is greater than D1
    3. Swap D1 and D2
    4. Reverse all digits to the right of D1's original index

Log in to reply
 

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