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.
Example 1:
Input: nums = [1,2,3] Output: [1,3,2]
Example 2:
Input: nums = [3,2,1] Output: [1,2,3]
Example 3:
Input: nums = [1,1,5] Output: [1,5,1]
Example 4:
Input: nums = [1] Output: [1]
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100
The description was taken from https://leetcode.com/problems/next-permutation/.
#O(N) Time, O(1) Space
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
def swap(left:int, right:int) -> None:
nums[left], nums[right] = nums[right], nums[left]
def reverse(left:int, right:int) -> None:
while left < right:
swap(left, right)
left += 1
right -= 1
pivot = None
for i in range(len(nums)-2, -1, -1):
if nums[i] < nums[i+1]:
pivot = i
break if pivot == None:
reverse(0, len(nums)-1)
return
for i in range(len(nums)-1, -1, -1):
if nums[i] > nums[pivot]:
swap(i, pivot)
break
reverse(pivot+1, len(nums)-1)
returnLet's start by looking at why the next permutation wouldn't be possible and work backward from there.
If we have the numbers: [5,4,3,2,2,1], we wouldn't be able to create the next permutation from this list because it is already the maximum permutation for this set of numbers.
In this scenario, the list of numbers would be monotonic non-increasing. Which would be monotonic non-decreasing moving from right to left. If this is the case, the numbers are already sorted in descending order so we can reverse the list for it to be in sorted ascending order.
Now let's look at a prior permutation of the previous set of numbers:
[2,2,1,5,4,3]
We know that from the beginning that we can't make the next permutation if we are moving from right to left through the array and can't find a value that isn't non-increasing, but here we found one.
[2,2,1,5,4,3]
The benefit of finding the first non-increasing value when traversing the array right to left is we passed a sorted partition of the array in doing so, and now know the length of the sorted partition.
[2,2,1,5,4,3]
Now, we have a split in our array which we will call a pivot.
From that split-point is where we will find the next permutation. If we have 221, and we are choosing between the remaining numbers in the set to create the next greater value, we would pick from the next greater value in the set of remaining numbers, three, to make 223.
Since we removed a one and placed a three, we now are missing a one from our set. We will place that one where we took the three from because it was the smallest value in the remaining set and placing a one there will keep that integrity non-decreasing integrity moving from right to left.
The reason this is important is that if we just swapped these two values and stopped we would have [2,2,3,5,4,1] which would be skipping [2,2,3,1,4,5], [2,2,3,1,5,4], [2,2,3,4,1,5], [2,2,3,4,5,1], and [2,2,3,5,1,4].
Look at the first number we skipped.
We can get that number from making the partition after the pivot the smallest version of itself, and since everything up to that point moving from right to left is non-decreasing, we can achieve that result by just reversing it, going back to the beginning of the explanation.
That is how we will solve this problem. We need to find a pivot point that will be the first non-decreasing value moving from right to left, swap that pivot point with the next greater value within the set of numbers after it, then reverse everything after that pivot point.
Let's start by creating a swap helper function that will take a left and a right pointer then swap the elements at these two indices within the input array.
def swap(left:int, right:int) -> None:
nums[left], nums[right] = nums[right], nums[left]
Next, we will create a reverse function that will take a left and right pointer and continuously swap each element within this range.
def reverse(left:int, right:int) -> None:
while left < right:
swap(left, right)
left += 1
right -= 1
After, let's create a pivot variable set to null, traverse the array backward to find the first non-increasing value then set the pivot to it.
pivot = None
for i in range(len(nums)-2, -1, -1):
if nums[i] < nums[i+1]:
pivot = i
break
If we couldn't set a pivot then we will reverse the array and return.
if pivot == None:
reverse(0, len(nums)-1)
return
Otherwise, we will find the first value greater than the pivot and swap these two values.
for i in range(len(nums)-1, -1, -1):
if nums[i] > nums[pivot]:
swap(i, pivot)
break
Now, all we need to do is reverse everything after the pivot and return.
reverse(pivot+1, len(nums)-1)
return