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