Next Permutation

Introduction

The Next Permutation problem is an important concept in algorithms. It helps us find the next lexicographically greater arrangement of numbers.

---

Problem Statement

Given an array of integers, rearrange them into the next greater permutation.

If no greater permutation exists, rearrange it to the lowest possible order (sorted in ascending order).

---

Approach

We follow these steps:

1. Find the first index i from the end such that:
   arr[i] < arr[i + 1]

2. If no such index exists:

   • Reverse the entire array (last permutation case)

3. Otherwise:

   • Find index j such that arr[j] > arr[i]
   • Swap arr[i] and arr[j]

4. Reverse the elements from i+1 to the end

---

Python Code

python
def nextPermutation(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: If found
    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 rest
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

    return nums

# Example
nums = [1, 2, 3]
print("Next Permutation:", nextPermutation(nums))


## Input
  [1,2,3]
## output
  [1,3,2]