• ``````def nextPermutation(self, nums):
i = l = len(nums)-1
while i > 0:
# find the right most pair where nums[i] > nums[i-1]
if nums[i] > nums[i-1]:
tmp = 0
for j in xrange(l, i-1, -1):
if nums[j] > nums[i-1]:
tmp = j
break
# exchange nums[i-1] and the right most element which larger than nums[i-1]
nums[i-1], nums[tmp] = nums[tmp], nums[i-1]
# reverse from i to the end
for j in xrange(i, 1+i+(l-i)/2):
nums[j], nums[l+i-j] = nums[l+i-j], nums[j]
break
i -= 1
# if nums are in descending order
if i == 0:
nums.reverse()``````

• Here is a revised version which look much better:

``````def nextPermutation(self, nums):
i = j = len(nums)-1
while i > 0 and nums[i] <= nums[i-1]:
i -= 1
if i > 0:
while nums[j] <= nums[i-1]:
j -= 1
nums[i-1], nums[j] = nums[j], nums[i-1]
nums[i:] = reversed(nums[i:])``````

• Creating `nums[i:]` violates the "do not allocate extra memory" requirement, though.

• Yes, indeed, it's just for convenience. Based on the requirement we can reverse in place:
for j in xrange(i, 1+i+(l-i)/2):
nums[j], nums[l+i-j] = nums[l+i-j], nums[j]

• Yeah, I've seen it in your original code. I think I'd prefer this, though:

``````    while i < l:
nums[i], nums[l] = nums[l], nums[i]
i += 1
l -= 1
``````

It's more lines, but much simpler.

• Or like this, also very simple:

``````    for j in xrange((l+1-i)/2):
nums[i+j], nums[~j] = nums[~j], nums[i+j]
``````