Python solution with detailed explanation


  • 0
    G

    Solution

    Next Permutation https://leetcode.com/problems/next-permutation/

    • The O(N) inplace algorithm is not easy. It is indeed tricky. The editorial has a nice explanation along with a nice animation.
    • Use the example: [1,5,8,4,7,6,5,3,1]
    • Start from the end and scan leftwards till you find the first number which breaks the decreasing sequence. In this case it is 4.
    • Now if we swap 4 and 7, we will definitely get a larger number than the current one. But that is not the next smallest number.
    • We want to replace 4 with a digit which is just larger than 4 - smallest number larger than 4 on right. That is 5. We swap the two and get: [1,5,8,5,7,6,4,3,1]
    • Now [1,5,8,5,7,6,4,3,1] > [1,5,8,4,7,6,5,3,1], but not the smallest number larger than it. If we reverse all digits after 5, we will get the first number in that sequence. [1,5,8,5,1,3,4,6,7]

    Test Cases:
    []
    [1]
    [2,1]
    [1,3,2]

    Implementation Code

        def nextPermutation(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            i = len(nums)-2
            while i >= 0 and nums[i] >= nums[i+1]:
                i = i - 1
            if i == -1:
                nums.sort()
            else:
                j = i+1
                while j < len(nums) and nums[j] > nums[i]:
                    j = j+1
                j = j-1
                nums[i], nums[j] = nums[j], nums[i]
                s,e = i+1, len(nums)-1
                while s < e:
                    nums[s], nums[e] = nums[e], nums[s]
                    s,e = s+1, e-1
            return
    

Log in to reply
 

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