[Leetcode]31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

This is a more ‘math’ problem and one good practice to solve it is to walk through examples and observe the patterns.

Logic

Let’s handle one example together so you could find the pattern.

6 5 4 8 7 5 1

Looking forward from the end of it, it’s easy to notice that there’s not much we can do about 8 7 5 1 as they are decreasing already. It means that the subarray 8 7 5 1 has reached its maximum, so we need to change the one before this subarray. Then reverse the subarray to set it to the minimum.

So the one to be changed is 4, and we need to swap it with 5, which is the first one that is larger than it. After swapping, we have:

6 5 5 8 7 4 1

As we mentioned, 8 7 4 1 needs to be reversed so we have:

6 5 5 1 4 7 8

Code

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = j = len(nums)-1
        while i > 0:
            if nums[i] > nums[i-1]:
                break
            i -= 1
        if i == 0:
            nums.reverse()
            return
        while nums[j] <= nums[i-1]:
            j -= 1
        nums[i-1],nums[j] = nums[j],nums[i-1]
        l,r = i,len(nums)-1
        while l < r:
            nums[l],nums[r] = nums[r],nums[l]
            l+=1
            r-=1

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments