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_biggercomes into play
- if an index is found, swap current element with the
- 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_nextflag 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