Next Permutation (Leetcode 31)

Problem Link: https://leetcode.com/problems/next-permutation/

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        
        # Step 1: Find i
        i=n-2
        while(i>=0 and nums[i]>=nums[i+1]):
            i-=1
        
        if(i<0):
            nums[:]=nums[::-1]
        else:
            # Step 2: Find j
            j=n-1
            while(j>=0 and nums[j]<=nums[i]):
                j-=1
            
            # Step 3: Swap nums[i], nums[j]
            nums[i],nums[j]=nums[j],nums[i]
            
            # Step 4: Reverse the array after i
            nums[:]=nums[:i+1]+nums[n-1:i:-1]

Last updated