31. Next Permutation

https://leetcode.com/problems/next-permutation/
Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        left = len(nums) - 1
        right = len(nums) - 1

        # Nums after left (not included) are not yet reach the max which is permutable
        while left > 0 and nums[left-1] >= nums[left]:
            left -= 1

        # The nums already reach the max, go back to first permutation
        if left == 0:
            self.reverse(nums, left, len(nums)-1)
            return

        # In the permutable zone, swap the left bound of next order head
        while nums[right] <= nums[left-1]:
            right -= 1

        nums[left-1], nums[right] = nums[right], nums[left-1]

        # Reverse the permutable zone order
        self.reverse(nums, left, len(nums)-1)

    def reverse(self, nums, left, right):
        stack = []
        for i in range(left, right+1):
            stack.append(nums[i])
        for i in range(left, right+1):
            nums[i] = stack.pop()
Python​

Python
