CA 12 - Next Permutation

Problem
Next Permutation
You are given an array of integers nums.
Your task is to find the next lexicographically greater permutation of the array.

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

Input: [1, 2, 3] → Output: [1, 3, 2]
Input: [3, 2, 1] → Output: [1, 2, 3]
Input: [1, 1, 5] → Output: [1, 5, 1]

Approach

Think of the array as a number that we want to slightly increase.We try to make the smallest possible change that results in a bigger permutation.

Steps:

1. Traverse from right and find the first index i such that
   nums[i] < nums[i + 1]

2. If such an index exists:

• Find the smallest element greater than nums[i] on the right side
• Swap them

1. Reverse the subarray from i + 1 to the end
2. If no such index exists, simply reverse the whole array

This ensures we get the next permutation in lexicographical order.

Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

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
    return nums
nums = [1, 2, 3]
print(nextPermutation(nums))