31. Next Permutation.py

# Time: O(n)
# Space: O(1)
# 31 Next Permutation
# Edge case 
'''
https://www.nayuki.io/res/next-lexicographical-permutation-algorithm/next-permutation-algorithm.png
'''

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        pivot, bigger = -1,0
        for i in xrange(len(nums) -1):
            if nums[i] < nums[i+1]:
                pivot = i
                
        if pivot == -1:
            nums.reverse()
            return 
        
        for i in xrange(pivot + 1, len(nums)):
            if nums[i] > nums[pivot]:
                bigger = i
            
        nums[pivot], nums[bigger] = nums[bigger], nums[pivot]
        nums[pivot + 1:] = nums[:pivot:-1]