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.

Solutions:

Next Permutation: Intuition and Optimal Approach

The Next Permutation problem asks you to rearrange numbers into the next greater permutation. If such an arrangement is not possible, you must rearrange it into the smallest possible order (sorted in ascending order).

Problem Understanding

Given an array of numbers, the goal is to modify it in-place so that it becomes the next lexicographically greater permutation.

Example:

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

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

Key Idea Behind the Algorithm

Instead of generating all permutations (which is very slow), the idea is to find a point where we can make a small increase and then adjust the rest of the array to be as small as possible.

Code

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:

        i = len(nums) - 1
        while i > 0 and nums[i-1] >= nums[i]:
            i -= 1

        if i < 1:
            nums[:] = nums[::-1]
        else:
            j = len(nums) - 1
            while nums[j] <= nums[i-1]:
                j -= 1
            nums[j], nums[i-1] = nums[i-1], nums[j]
            nums[i:] = nums[i:][::-1]

Step-by-Step Explanation

Step 1: Find the Break Point

i = len(nums) - 1
while i > 0 and nums[i-1] >= nums[i]:
i -= 1

1.first

1. We traverse from the right side to find the first position where the order is increasing. This position (i-1) is called the pivot.
2. This step helps identify where we can make the next bigger permutation.
3. Time complexity for this step is O(n), and space complexity is O(1).

Step 2: Check if No Greater Permutation Exists
if i < 1:
nums[:] = nums[::-1]

1. If no pivot is found, it means the array is in descending order. In that case, we reverse the array to get the smallest permutation.
2. Time complexity is O(n), and space complexity is O(1) since the reversal is done in-place.

Step 3: Find the Next Greater Element

j = len(nums) - 1
while nums[j] <= nums[i-1]:
j -= 1

Step 4: Swap Elements
nums[j], nums[i-1] = nums[i-1], nums[j]

1. We swap the pivot with the element found in the previous step to increase the number slightly.
2. Time complexity is O(1), and space complexity is O(1).

Step 5: Reverse the Remaining Elements
nums[i:] = nums[i:][::-1]

The elements to the right of the pivot are in descending order. Reversing them makes them the smallest possible, ensuring the result is the next permutation.
Time complexity is O(n), and space complexity is O(1)
.
Why This Approach Is Better?

1. This approach is optimal because it avoids generating all permutations, which would take factorial time. Instead, it works in linear time and modifies the array in-place.

2. It is efficient, clean, and widely used in interviews because it demonstrates a strong understanding of array manipulation and lexicographic ordering