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:
        if nums[i] < nums[i + 1]:
            break
        i -= 1
    if i >= 0:
        j = n - 1
        while j > i:
            if nums[j] > nums[i]:
                break
            j -= 1

        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp
    start = i + 1
    end = n - 1
    while start < end:
        temp = nums[start]
        nums[start] = nums[end]
        nums[end] = temp
        start += 1
        end -= 1

• We are given numbers like [1,2,3] and the goal is to find the next bigger arrangement using the same numbers, not just any bigger one but the immediate next.
• For example, 123 becomes 132, then 132 becomes 213, and so on.
• So instead of trying all permutations, we think of how to make the smallest possible change to get a bigger number.
• The idea is to start from the right end because changes on the right affect the number the least.
• We move from right to left and look for the first place where the order breaks, meaning a number is smaller than the one after it.
• In [1,2,3], we see that 2 < 3, so that’s our point of change and we mark the index of 2. Now we know we can make the number bigger from here.
• Next, we look at the right side of this index and try to find a number just bigger than 2. In this case, we only have 3, which is perfect.
• Then we swap 2 and 3, so the array becomes [1,3,2].
• But we are not done yet because after swapping, the right side might not be in the smallest possible order.
• Since we want the next immediate permutation, we need to make the right side as small as possible, so we sort (or reverse, since it’s already in decreasing order) everything to the right of the index.
• Here it’s just [2], so no change is needed. Finally, we get [1,3,2], which is the next permutation.