Next Permutation

Arrangement

Problem

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

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

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

For example:

Input: nums = [1,2,3]
Output: [1,3,2]

Input: nums = [3,2,1]
Output: [1,2,3]

Input: nums = [1,1,5]
Output: [1,5,1]

Input: nums = [1]
Output: [1]

Thought Process

• Notice how that a section that is strictly decreasing has exhausted itself and reached its last placement, i.e. the highest permutation available for that section

• Since a strictly decreasing section means that that section is on it's last/highest permutation, this means the overall next permuation in the array has to begin in a placement where an element is at the beginning of an ascending order section, i.e. the element before the strictly decreasing section.

Example: 1 2 3 ---> 1 3 2

Example: 1 2 3 6 5 4 ---> 1 2 4 3 5 6 4

(Bolded number is the slot that still has options to explore)

• Why we choose an element before a strictly decreasing section is because this slot/index still has options to explore and has not exhausted all of its permuations because it is not the highest permutation for this section which includes the slot.

• The slot we identify as the next permutation has to be swapped with the rightmost first larger number, since this will produce the next greater permutation

  • w

• If we identify the whole array being in descending order, then we just have to flip the array horizontally to recieve the lowest possible order

Solution

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
   
        i = len(nums) - 2 
        
        #finding number that's in ascending order
        while(i >= 0 and nums[i] >= nums[i+1]):
            i-=1
            
        #if the array is in the highest perm.
        if(i==-1):
            for n in range(len(nums)//2):
                temp = nums[n]
                nums[n] = nums[len(nums)-1-n]
                nums[len(nums)-1-n] = temp
            return
         
        #finding the rightmost first larger number
        k = len(nums)-1
        while(nums[k] <= nums[i]):
            k-=1
            
        nums[i], nums[k] = nums[k], nums[i]
        
        l = i+1
        r = len(nums)-1
        
        #rearranging the numbers in our new permutation
        while l <= r:
            nums[l], nums[r] = nums[r], nums[l]
            l+=1
            r-=1
        
        return nums  
        

Key Facts

• We are looking for a section that is strictly decreasing, as this section is on it's last permuation that is the greatest

• A section that is strictly decreasing means it is on it's highest permuation. The slot right before this means this is the beginning positon of the next permuation

• We need to switch the element right before the decreasing section (i.e. an element that's the start of ascending) with the rightmost first larger number

Time Complexity

• Time: $O(n)$

• Space: $O(1)$