CA 12 - Next Permutation

Problem

Given an array of integers nums, the task is to find the next lexicographically greater permutation.

If such a permutation is not possible, rearrange the array into the lowest possible order (ascending order).

The replacement must be done in-place using constant extra memory.

Output

Example 1
Output: [1, 3, 2]
Example 2
Output: [1, 2, 3]
Example 3
Output: [1, 5, 1]

My Approach

To solve this problem, I followed a step-by-step method.

First, I find the first index from the end where the order is decreasing.

Then, I find the element just greater than this element on the right side and swap them.

After that, I reverse the remaining part of the array to get the next smallest arrangement.

This works because:

Swapping increases the number slightly
Reversing ensures the smallest possible order after the swap

This approach is efficient because:

It requires only one traversal
It uses constant extra space
Code

def next_permutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    left = i + 1
    right = len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums