Leetcode 31. Next Permutation - Python-CodePudding

I am trying to solve a Leetcode problem:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order). The replacement must be in place and use only constant extra memory.

I don't understand why I am getting an error saying "list index out of range" on line 17 (i marked as "error"). Test cases were all working.

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
    
        # pivot
        r = len(nums) - 1
        while nums[r-1] > nums[r] and r > 0:
            r -= 1
        pivot = r 

        if pivot == 0: 
            nums.sort()
            return 

        # swap
        else: 
            swap = len(nums) - 1
            while nums[pivot-1] >= nums[swap]: # error (line 17)
                swap -= 1
            nums[pivot-1], nums[swap] = nums[swap], nums[pivot-1]

            # reverse
            nums[pivot:]  = sorted(nums[pivot:])

CodePudding user response：

The immediate issue is that swap can become less than 0, for inputs like [1, 1], to prevent this change:

while nums[pivot-1] >= nums[swap]:

to:

while nums[pivot-1] >= nums[swap] and swap >= 0:

Furthermore, you also want to use >= rather than > in your pivot calculation loop, so that, you don't prematurely exit the loop when two adjacent elements are the same (e.g., [2, 1, 1]) i.e., change:

while nums[r-1] > nums[r] and r > 0:

to:

while nums[r-1] >= nums[r] and r > 0: