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

  • 0

    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
                    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"
            if not has_next:
                nums[:] = sorted(nums) # if no "next permutation" available, sort it in ascending order as is instructed in the problem

Log in to reply

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