# Simple easy to understand python solution, beats 94%, open to critic!

• The gist is to start from right most, and find the smallest possible change to reach "next permutation".

Here we use a helper function `min_bigger` to find the minimum biggest number to right of a given index.

Here are the steps:

• scan right to left and find an index where the number has an element to the right that is greater, if there are multiple, only use the smallest one (this is where the helper function `min_bigger` comes into play
• if an index is found, swap current element with the `min_bigger` element
• then to conform with the "next permutation", we sort partially the array starting from current element (non-inclusive)
• in the end we check if the `has_next` flag is still False, if it is, sort the whole array in ascending order

This is using a bit of backtracking, so its supposed `O(n^2)` runtime isn't that obvious. But please point out where I could further improve this algorithm, I'm pretty sure the 94% is me getting luck.

``````class Solution(object):
def nextPermutation(self, nums):
# """
# :type nums: List[int]
# :rtype: void Do not return anything, modify nums in-place instead.
# """
def min_bigger(num_arr, l_idx):
r_idx = -1
min_bigger = float('inf')
for i in range(l_idx, len(num_arr)):
num = num_arr[i]
if num > nums[l_idx] and num < min_bigger:
min_bigger = num
r_idx = i
return r_idx
has_next = False
idx = len(nums) - 1
while idx >= 0:
right = min_bigger(nums, idx)
if right == -1:
idx -= 1
continue
else:
nums[right], nums[idx] = nums[idx], nums[right]
has_next = True
nums[idx+1:] = sorted(nums[idx+1:]) # sort the rest of the list to conform with "minimum next permutation"
break
if not has_next:
nums[:] = sorted(nums) # if no "next permutation" available, sort it in ascending order as is instructed in the problem``````

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