Next lexicographical permutation algorithm

Related problem

31. Next Permutation

A good explanation

Image is from:

My code based on this algorithm

class Solution:
def nextPermutation(self, nums: List[int]) -> None:
Do not return anything, modify nums in-place instead.
if len(nums)<=1:return nums
j = len(nums)-2
while j>=0:
if nums[j]<nums[j+1]:
j -= 1
pivot = j
val = nums[j]
this_min = float('inf')
target_k = 0
for k in range(j+1, len(nums)):
if val<nums[k]<=this_min:
target_k = k
nums[pivot], nums[target_k] = nums[target_k], nums[pivot]
l, r = pivot+1, len(nums)-1
while l<r:
nums[l], nums[r] = nums[r], nums[l]

Code from a post

def nextPermutation(self, nums):
i = j = len(nums)-1
while i > 0 and nums[i-1] >= nums[i]:
i -= 1
if i == 0: # nums are in descending order
k = i - 1 # find the last "ascending" position
while nums[j] <= nums[k]:
j -= 1
nums[k], nums[j] = nums[j], nums[k]
l, r = k+1, len(nums)-1 # reverse the second part
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l +=1 ; r -= 1



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi