Next Permutation

Attempt 1

• gyan_pelo
• So for this one there can be thebrute_force way where all subsets of the array are calculated and then the second largest number is picked, that will make it a 2^N problem.
• Can any number be swapped so thetime_complexity is n?

Attempt 2

• Bubble sort
• [1, 6, 3, 2]
• right_to_left_traversal
• write_explainatory_code the variable names i, j, k are confusing, not sure why people will write these, they can be converted later like this by compiler or minifier.

Attempt 3

• TC: O(n)

def nextPermutation(self, nums):
    # Step 1: Find the first index from the right where the elements are in non-decreasing order.
    first_non_increasing = second_pointer = len(nums) - 1
    
    while first_non_increasing > 0 and nums[first_non_increasing - 1] >= nums[first_non_increasing]:
        first_non_increasing -= 1
    
    # Step 2: If the entire list is in descending order, reverse the list and return.
    if first_non_increasing == 0:
        nums.reverse()
        return
    
    # Step 3: Find the last "ascending" position.
    pivot_index = first_non_increasing - 1
    
    # Step 4: Find the smallest element in the right part that is greater than the pivot.
    while nums[second_pointer] <= nums[pivot_index]:
        second_pointer -= 1
    
    # Step 5: Swap the pivot and the smallest greater element.
    nums[pivot_index], nums[second_pointer] = nums[second_pointer], nums[pivot_index]
    
    # Step 6: Reverse the second part to make it the smallest possible permutation.
    left, right = pivot_index + 1, len(nums) - 1
    
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
 

Explanation by ChatGPT

Now, let’s perform a dry run with the input [1, 3, 6, 4, 2]:

1. Initialization:

   • first_non_increasing = 4 (last index)
   • second_pointer = 4 (last index)

2. Finding the first index in non-decreasing order:

   • Iterating from right to left:
     • nums[3] = 4 is not greater than or equal to nums[4] = 2, so decrement first_non_increasing.
     • nums[2] = 6 is greater than or equal to nums[3] = 4, so stop.

3. Check if the entire list is in descending order:

   • first_non_increasing is not 0, so continue.

4. Find the last “ascending” position (pivot_index):

   • pivot_index = first_non_increasing - 1 = 3.

5. Find the smallest element in the right part that is greater than the pivot:

   • Iterating from right to left:
     • nums[4] = 2 is not greater than nums[3] = 4, so decrement second_pointer.
     • nums[3] = 4 is greater than nums[2] = 6, so stop.

6. Swap the pivot and the smallest greater element:

   • Swap nums[3] and nums[4]: nums = [1, 3, 6, 2, 4].

7. Reverse the second part to make it the smallest possible permutation:

   • Reverse the subarray from index pivot_index + 1 to the end: nums = [1, 3, 2, 4, 6].

The modified nums list is [1, 3, 2, 4, 6], which is the next lexicographically greater permutation of the input [1, 3, 6, 4, 2].