[LeetCode] 31. Next Permutation

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

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        def reverse(nums, start, end):
            left = start
            right = end - 1

            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        if len(nums) < 2:
            return nums

        i = len(nums) - 2

        # find pivot which is the first number from back where acending order starts 
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1

        if i == -1:
            nums.sort()
            return nums

        # find the first number from back which is just larger than the pivot number
        j = len(nums) - 1
        while j > i and nums[j] <= nums[i]:
            j -= 1

        # swap
        nums[i], nums[j] = nums[j], nums[i]

        # reverse the right of pivot
        reverse(nums, i+1, len(nums))
        return nums