Next Permutation

Problem Statement

Given an array of integers representing a permutation, rearrange the array into the next lexicographically greater permutation.

If such an arrangement is not possible, rearrange it as the lowest possible order which is sorted in ascending order.

---

Examples

Input
arr = [1, 2, 3]

Output
[1, 3, 2]

---

Input
arr = [3, 2, 1]

Output
[1, 2, 3]

---

Input
arr = [1, 1, 5]

Output
[1, 5, 1]

---

Approach

The idea is to find a position where the order can be increased and then rearrange the remaining part.

---

Steps

1 Traverse from right and find the first index i such that arr[i] is less than arr[i + 1]
2 If no such index exists, reverse the entire array
3 Otherwise, find index j such that arr[j] is just greater than arr[i] from the right side
4 Swap arr[i] and arr[j]
5 Reverse the subarray from i plus 1 to end

---

Code

```python id="np1"
def nextPermutation(arr):
n = len(arr)
i = n - 2

while i >= 0 and arr[i] >= arr[i + 1]:
    i -= 1

if i >= 0:
    j = n - 1
    while arr[j] <= arr[i]:
        j -= 1
    arr[i], arr[j] = arr[j], arr[i]

left = i + 1
right = n - 1

while left < right:
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1

return arr

---

## Explanation

The algorithm first finds a point where the sequence stops increasing from the right. Then it swaps that element with the next greater element. Finally, it reverses the remaining part to get the next smallest permutation.

---

## Expected Output

Input
arr = [1, 2, 3]

Output
[1, 3, 2]

---

## Conclusion

Next Permutation is an important problem that helps in understanding permutations and array manipulation. It is widely used in problems involving ordering and combinations.

Practice this problem to improve your understanding of sequences and in place operations.