# Two-pointer solution in python with detail expalanation

• Credit goes to http://blog.csdn.net/m6830098/article/details/17291259

``````class Solution(object):
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
# Use two-pointers: two pointers start from back
# first pointer j stop at descending point
# second pointer i stop at value > nums[j]
# swap and sort rest
if not nums: return None
i = len(nums)-1
j = -1 # j is set to -1 for case `4321`, so need to reverse all in following step
while i > 0:
if nums[i-1] < nums[i]: # first one violates the trend
j = i-1
break
i-=1
for i in xrange(len(nums)-1, -1, -1):
if nums[i] > nums[j]: #
nums[i], nums[j] = nums[j], nums[i] # swap position
nums[j+1:] = sorted(nums[j+1:]) # sort rest
return``````

• It still seems like an O(n log n) solution. Anyone did it in linear time?

• similar idea, without sorting

``````def nextPermutation(self, nums):
for i in range(len(nums)-1, -1, -1):
if i-1 >=0 and nums[i] > nums[i-1]:
for j in reversed(range(i,len(nums))):
if nums[j] > nums[i-1]:
nums[i-1], nums[j] = nums[j], nums[i-1]
break
nums[i:] = nums[i:][::-1]
break
else:
nums = nums.reverse()``````

• see my reply as a separate answer. O(n) time complexity, I used slicing, but it can be replaced by manually swapping to achieve O(1) space complexity.

• ``````    def nextPermutation(self, nums):
i = len(nums)-1
while i > 0:
if nums[i] > nums[i-1]:
for j in xrange(len(nums)-1, 0, -1):
if nums[j] > nums[i-1]:
nums[j], nums[i-1] = nums[i-1], nums[j]
break
break
i -= 1
nums[i:] = nums[i:][::-1]``````

• Actually, you use O(n) space because `nums[i:][::-1]` makes a copy of `nums[i:]` and reverse it.

• @pennlio
Does this line do in-place and not allocate extra memory?
``` nums[j+1:] = sorted(nums[j+1:]) # sort rest ```

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