🔁 Next Permutation (Step-by-Step Explanation)

The Next Permutation problem is a classic algorithm question that helps you understand how to generate the next lexicographically greater arrangement of numbers.

📌 Problem Statement

Given an array nums, rearrange it into the next greater permutation.

If such a permutation is not possible (i.e., the array is in descending order), rearrange it into the smallest possible order (ascending).

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

🔍 Examples

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

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

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

🧠 Intuition

To find the next permutation:

We need to find a position where we can increase the number slightly
Then rearrange the remaining part to get the smallest possible order

🔄 Approach (Optimal Algorithm)

Step-by-Step:

Find the first decreasing element from the right
(index i such that nums[i] < nums[i+1])
If such an index exists:

Find the element just greater than nums[i] from the right
Swap them

Reverse the part of the array after index i

💻 Python Code

def next_permutation(nums):
n = len(nums)
i = n - 2

# Step 1: find decreasing element
while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1

# Step 2: swap with next greater element
if i >= 0:
    j = n - 1
    while nums[j] <= nums[i]:
        j -= 1
    nums[i], nums[j] = nums[j], nums[i]

# Step 3: reverse the remaining array
left, right = i + 1, n - 1
while left < right:
    nums[left], nums[right] = nums[right], nums[left]
    left += 1
    right -= 1

return nums