Python solution doesn't require extra memory. 58ms.

• list.sort() and qsort() are used because sorted() is not in-place sort.

``````    def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = len(nums)-1
# find position i which i-1th element is less than ith element
while i > 0 and nums[i-1] >= nums[i]:
i -= 1
# if nums is sorted in descending order, return sorted array in ascending order
if i == 0:
nums.sort()
else:
# sort i to end
self.qsort(nums, i, len(nums)-1)
# switch i-1 and smallest one bigger than i-1th element
j = i
while j < len(nums) and nums[j] <= nums[i-1]:
j += 1
if j < len(nums) and nums[j] > nums[i-1]:
nums[j], nums[i-1] = nums[i-1], nums[j]
# qsort implementation in python
def partition(self, nums, begin, end):
pivot = begin
for i in range(begin+1,end+1):
if nums[i] <= nums[begin]:
pivot += 1
nums[i], nums[pivot] = nums[pivot], nums[i]
nums[pivot], nums[begin] = nums[begin], nums[pivot]
return pivot
def qsort(self, nums, begin, end):
if begin >= end:
return
pivot = self.partition(nums, begin, end)
self.qsort(nums, begin, pivot-1)
self.qsort(nums, pivot+1, end)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.