Next Permutation in an Array

Problem Statement:
Given an array of integers, find its next lexicographically greater permutation. If such permutation does not exist, rearrange the array into the smallest possible order.

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

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

Approach:
To find the next permutation, we follow these steps:

• Traverse the array from the end and find the first element that is smaller than its next element.
• Again traverse from the end and find the first element greater than the element found in step 1.
• Swap both elements.
• Reverse the part of the array to the right of the swapped element.
• This gives the immediate next lexicographical permutation.

Code:

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 = i + 1
right = n - 1
while left < right:
    nums[left], nums[right] = nums[right], nums[left]
    left += 1
    right -= 1

Explanation:
The algorithm finds the first position from the right where the order breaks. Then it swaps that element with the next greater element on its right. Finally, it reverses the remaining part to get the smallest possible larger permutation.

Time Complexity:
O(n)

Space Complexity:
O(1)