Next Permutation (in Python)

Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

Solution

Approach 1 : Brute Force

Complexity Analysis

•Time complexity : (O(n!)). Total possible permutations is n!.

•Space complexity : (O(n)). Since an array will be used to store the permutations.

---

Approach 2 : Single Pass Approach

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
 
        if n < 2 :
            return nums
 
        inverse = -1
        i = n-2
 
        # 1. Finding first decreasing element
        while i >= 0 :
            if nums[i] < nums[i+1] :
                inverse = i
                break
            i -= 1
        
        if inverse < 0 :
            nums.sort()
            i = 0
            while nums[i] == 0 :
                i += 1
            if i != 0 :
                nums[0], nums[i] = nums[i], nums[0]
            return nums
 
        i = n-1
 
        # 2. Finding number just larger than the inverse element
        while i >= 0 :
            if nums[inverse] < nums[i] :
                nums[inverse], nums[i] = nums[i], nums[inverse]
                break
            i -= 1
        
        # 3. Reverse [inverse + 1 ~ ] elements
        nums[inverse+1:] = reversed(nums[inverse+1:])
        return nums

Complexity Analysis

•Time complexity : (O(n)). In worst case, only two scans of the whole array are needed.

•Space complexity : (O(1)). No extra space is used. In place replacements are done.

Source

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