# Beat 84% Python code. With idea description

• Main idea: loop through the list backwards and find the first element such that nums[i - 1] < nums[i]. We call i - 1 the pivot point. We find the minimum element in nums[pivotPoint:] such that it is bigger than nums[pivotPoint]. We call this pivotPoint2. We swap pivotPoint and pivotPoint2, then we sort the nums[pivotPoint:] in place.

Example:
5, 7, 9, 4, 1
loop backwards: 1,4,9,7. Stop, since 9 > 7. Now 7 is pivot point. In [9,4,1], 9 is the minimum number which is biggeer than 7. we swap 9 and 7: 5,9,7,4,1. Then we sort [7,4,1] in place, we got [1,4,7], nums becomes [5,9,1,4,7].

Finished

O(n + nlogn) = O(nlogn), apprently.

``````class Solution(object):
def nextPermutation(self, nums):
L = len(nums)
pivotPoint = -1
for i in range(L - 1, 0, -1):
if nums[i - 1] < nums[i]:
pivotPoint = i - 1
break
if pivotPoint == -1:
nums.sort() #O(nlogn)
return
minn = max(nums) # O(n)
pivotPoint2 = -1
for i in range(pivotPoint, L):
if nums[i] > nums[pivotPoint] and nums[i] <= minn:
minn = nums[i]
pivotPoint2 = i
buff = nums[pivotPoint2]
nums[pivotPoint2] = nums[pivotPoint]
nums[pivotPoint] = buff
nums[pivotPoint + 1:] = sorted(nums[pivotPoint + 1:]) # in place
return

``````

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