10-line Python solution, consider it as carry in addition, 60ms


  • 1
    K

    Current permutation should share longest prefix with next permutation and it's very similar to a carry in addition. Three steps: 1) from right to left find the longest increasing sequence, 2) carry to the previous number, 3) reverse the increasing sequence.

    def nextPermutation(self, nums):
        # from right to left find longest increasing sequence
        i = len(nums) - 1
        while i > 0 and nums[i - 1] >= nums[i]: i -= 1
        # swap nums[i - 1] and min(number in nums[i...end] which is larger than nums[i - 1])
        # consider it as a carry to nums[i - 1]
        if i > 0:
            j, pre = len(nums) - 1, nums[i - 1]
            while j >= i and nums[j] <= pre: j -= 1
            nums[i - 1], nums[j] = nums[j], nums[i - 1]
        # reverse nums[i...end]
        k = len(nums) - 1
        while i < k:
            nums[i], nums[k] = nums[k], nums[i]
            i, k = i + 1, k - 1

Log in to reply
 

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