# Python solution with detailed explanation

• Solution

Next Permutation https://leetcode.com/problems/next-permutation/

• The O(N) inplace algorithm is not easy. It is indeed tricky. The editorial has a nice explanation along with a nice animation.
• Use the example: [1,5,8,4,7,6,5,3,1]
• Start from the end and scan leftwards till you find the first number which breaks the decreasing sequence. In this case it is 4.
• Now if we swap 4 and 7, we will definitely get a larger number than the current one. But that is not the next smallest number.
• We want to replace 4 with a digit which is just larger than 4 - smallest number larger than 4 on right. That is 5. We swap the two and get: [1,5,8,5,7,6,4,3,1]
• Now [1,5,8,5,7,6,4,3,1] > [1,5,8,4,7,6,5,3,1], but not the smallest number larger than it. If we reverse all digits after 5, we will get the first number in that sequence. [1,5,8,5,1,3,4,6,7]

Test Cases:
[]
[1]
[2,1]
[1,3,2]

Implementation Code

``````    def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = len(nums)-2
while i >= 0 and nums[i] >= nums[i+1]:
i = i - 1
if i == -1:
nums.sort()
else:
j = i+1
while j < len(nums) and nums[j] > nums[i]:
j = j+1
j = j-1
nums[i], nums[j] = nums[j], nums[i]
s,e = i+1, len(nums)-1
while s < e:
nums[s], nums[e] = nums[e], nums[s]
s,e = s+1, e-1
return
``````

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