Sources: leetcode 31

Rating: medium

Given a list **nums**, re-arrange the numbers into the lexicographically next greater permutation of numbers. If this is not possible, rearrange it as the lowest possible order (sorted in ascending order). Perform the replacement in-place with constant extra memory.

def nextPermutation(nums: List[int]) -> None: # modify nums in-place into next permutation, do not return anything

**Solution**

First, if there are less than 2 values in **nums**, no change can be made.

def nextPermutation(nums): if len(nums) < 2: return # modify nums in-place into next permutation, do not return anything

Next, the trick is to realize what the exactly the “next permutation” is and how to find it. To find the next largest permutation, the arrangement occurs at the right most instance of a digit being less than the one immediately right of it. Use an index **i** starting from the end of **nums** and iterating left searching for the first instance.

def nextPermutation(nums): if len(nums) < 2: return i = len(nums) - 2 while i >= 0 and nums[i+1] <= nums[i]: i -= 1 # modify nums in-place into next permutation, do not return anything

To begin modifying into the next largest permutation, this found value at **nums[i]** must be swapped with the next largest value to the right of it. Use an index **j** starting from the end of the list **nums** and iterating left searching for the next largest value. Once the two indices **i** and **j** are found, transforming to the next largest iteration involves swapping the values at **nums[i]** and **nums[j]** and then reversing the order of all the digits from **i+1** onward.

def nextPermutation(nums): # define swap # define reverse if len(nums) < 2: return i = len(nums) - 2 while i >= 0 and nums[i+1] <= nums[i]: i -= 1 if i >= 0: j = len(nums) - 1 while j >= 0 and nums[j] <= nums[i]: j -= 1 swap(nums, i, j) reverse(nums, i+1)

Defining **reverse** is relatively straightforward. Using two indices **i** and **j** starting from opposite ends of the list, **swap** the values while incrementing **i** and **j** until they cross one another.

def nextPermutation(nums): # define swap def reverse(nums, start): i, j = start, len(nums) - 1 while i < j: swap(nums, i, j) i += 1 j -= 1 if len(nums) < 2: return i = len(nums) - 2 while i >= 0 and nums[i+1] <= nums[i]: i -= 1 if i >= 0: j = len(nums) - 1 while j >= 0 and nums[j] <= nums[i]: j -= 1 swap(nums, i, j) reverse(nums, i+1)

Defining the **swap** function is a trivial switch in the values between **nums[i]** and **nums[j]**.

**Final Code**

def nextPermutation(nums): def swap(nums, i, j): nums[i], nums[j] = nums[j], nums[i] def reverse(nums, start): i, j = start, len(nums) - 1 while i < j: swap(nums, i, j) i += 1 j -= 1 if len(nums) < 2: return i = len(nums) - 2 while i >= 0 and nums[i+1] <= nums[i]: i -= 1 if i >= 0: j = len(nums) - 1 while j >= 0 and nums[j] <= nums[i]: j -= 1 swap(nums, i, j) reverse(nums, i+1)