Simple Python 2-pass method

  • 1

    search from end to beginning:

    1st pass: find nums[i] > nums[i-1]. (so nums[i:] is in decreasing order)

    2nd pass: from nums[i:], find a minimum number that is bigger than nums[i-1], swap with nums[i-1]

    reverse num[i:] to make it increasing.

    Note that if num[:] is decreasing, reverse num[:]

    def nextPermutation(self, nums):
        for i in range(len(nums)-1, -1, -1):
            if i > 0 and nums[i] > nums[i-1]:  # 1nd condition is met
                for j in reversed(range(i,len(nums))):
                    if nums[j] > nums[i-1]:    # 2nd condition is met
                        nums[i-1], nums[j] = nums[j], nums[i-1]
        nums[i:] = nums[i:][::-1]

Log in to reply

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