Next Permutation

The next permutation question is a leetcode question that is works on finding the next lexogaphically greater permutation combination
**
When does the permutation changes? or increase?

it increases when a number on the left is smaller than a number on the right

let the given array be

arr = [1, 2, 3]

the next permutation in sorted way are

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

so when the question is What is the next permutation of [2,1,3]?, the answer will be [2,3,1]

Approach to the solve the question

Find first decreasing element from right → swap → reverse the rest
this way we find the next permutation

arr = [1, 3, 5, 4, 2]

Step 1 : to find where there is change when we *look right to left *

   2<4
   4<5
   but 3 > 5

so this is where we can make the array slighly greater

step 2: make the array slighly greater

so we find element in right of 3 **
**smallest number greater than 3
so we swap with element 4

swap 3 and 4 -> [1,4,5,3,2]

step 3: reverse the rest of the array
that in the array [1,4,5,3,2]

[5,3,2] -> [2,3,5]

final array = [1,4,2,3,5]

Algorithm

def nextPermutation(nums):
        n = len(nums)

        # Step 1: find pivot
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        # Step 2: find next greater element
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        # Step 3: reverse right part
        left = i + 1
        right = n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1