Python solution 49 ms


  • 0
    I

    The idea of this solution is to start from the end of the array and decrease current index while the next number is greater than the previous one. Then we have to reverse this part and do a swap. As a result we have a very elegant solution:

    class Solution(object):
        def nextPermutation(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            if not nums:
                return
            i = len(nums) - 1
            while i > 0 and nums[i - 1] >= nums[i]:
                i -= 1
            nums[i:] = reversed(nums[i:])
            if i > 0:
                k = i
                pivot = nums[i - 1]
                while k < len(nums) - 1 and nums[k] <= pivot:
                    k += 1
                if nums[k] != pivot:
                    nums[k], nums[i - 1] = nums[i - 1], nums[k]
    

Log in to reply
 

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