Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

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

Example 1:

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

Example 2:

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

Example 3:

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

Next Permutation

Given an array of integers nums, the goal is to find the next permutation of nums in lexicographical order. If no such permutation exists, rearrange the array in ascending order. This must be done in-place with constant extra memory.

Naive Approach (Brute Force)

The most straightforward approach would be to generate all possible permutations of the array, sort them lexicographically, and then find the next permutation after the given input array. However, this is highly inefficient.

1. Generate all permutations of nums. This can be done recursively.
2. Sort the generated permutations.
3. Find nums within the sorted list of permutations.
4. Return the next permutation. If nums is the last element, return the first permutation.

import itertools

def next_permutation_naive(nums):
    permutations = sorted(list(itertools.permutations(nums)))
    
    for i in range(len(permutations)):
        if permutations[i] == tuple(nums):
            return list(permutations[(i + 1) % len(permutations)])

This approach has a time complexity of O(n! * n log n) due to generating all permutations and sorting them. This is not efficient for larger arrays.

Optimal Approach

The optimal approach involves a few key steps to find the next permutation in-place:

1. Find the first decreasing element from the right: Starting from the end of the array, find the first index i where nums[i] < nums[i+1]. If no such index exists, the array is in descending order, and we need to reverse it to get the smallest permutation.
2. Find the smallest element to the right of i that is greater than nums[i]: Search the subarray to the right of i to find the smallest element nums[j] that is greater than nums[i].
3. Swap nums[i] and nums[j]: Exchange these two elements.
4. Reverse the subarray to the right of i: This ensures that the subarray is in ascending order, making the overall permutation the next lexicographical permutation.

def next_permutation(nums):
    n = len(nums)
    
    # Step 1: Find the first decreasing element from the right
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    
    if i >= 0:
        # Step 2: Find the smallest element to the right of i that is greater than nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        
        # Step 3: Swap nums[i] and nums[j]
        nums[i], nums[j] = nums[j], nums[i]
    
    # Step 4: Reverse the subarray to the right of i
    left = i + 1
    right = n - 1
    while left < right>0:
        return 0

Edge Cases

1. Empty Array: If the input array is empty, there is nothing to do. The function should return without modification.
2. Single Element Array: If the array contains only one element, it is already in its smallest and largest permutation, so no change is needed.
3. Array in Descending Order: If the array is in descending order, it has the largest possible permutation. In this case, we simply reverse the array to get the smallest permutation (ascending order).
4. Array Already in Ascending Order: The algorithm handles this case gracefully by finding the first decreasing element from the right and proceeding accordingly.

Example Walkthrough

Consider the array nums = [1, 2, 3]. Here's how the algorithm would proceed:

1. i starts at n - 2 = 1. nums[1] < nums[2] (2 < 3), so i remains 1.
2. j starts at n - 1 = 2. nums[2] > nums[1] (3 > 2), so j remains 2.
3. Swap nums[1] and nums[2]: nums becomes [1, 3, 2].
4. Reverse the subarray to the right of i (which is just nums[2]): No change needed.

The result is [1, 3, 2], which is the next permutation.

Now consider nums = [3, 2, 1].

1. i starts at n - 2 = 1. nums[1] >= nums[2] (2 >= 1), so i becomes 0. nums[0] >= nums[1] (3 >= 2), so i becomes -1.
2. Since i < 0, reverse the entire array. The result is [1, 2, 3].