CA 12 - Next Permutation

Problem Statement: here

PS Understanding:
We have to find the arrangement of numbers that is immediately bigger than the current one.

Solution:

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

    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]

    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

• We have numbers like: [1, 2, 3] and we want to make the next bigger arrangement using the same numbers. Example: 123 → next is 132 132 → next is 213 213 → next is 231

1. Start from the right end and check if the number before is less than it.
eg. in [1,2,3]
find where left < right
2 < 3 → this is the spot
So mark index of 2

2. Find a slightly bigger number on the right
Now look to the right of 2: [3]
Find a number just bigger than 2 → that is 3.

3. Swap them
Swap 2 and 3
[1, 3, 2]

4. Fix the right side
After swapping, take everything to the right and sort it in increasing order
Here it's just [2], so no change
Final answer:
[1, 3, 2]