Next Permutation

Problem Statement

A permutation of an array is an arrangement of its elements in a sequence.

The next permutation is the next lexicographically greater arrangement of numbers.

If such an arrangement is not possible (i.e., the array is in descending order), then rearrange it into the lowest possible order (ascending order).

Important Conditions:

The replacement must be done in-place
Only constant extra memory should be used
Example 1

Input:

nums = [1,2,3]

Output:

[1,3,2]
Example 2

Input:

nums = [3,2,1]

Output:

[1,2,3]

Explanation:
Since the array is in descending order, no greater permutation exists.
So we rearrange it into ascending order.

Example 3

Input:

nums = [1,1,5]

Output:

[1,5,1]
Understanding Lexicographical Order

Lexicographical order means dictionary order.

For example:

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Each arrangement is compared from left to right.

Efficient Approach (One Pass from Right)

To find the next permutation:

Step 1: Find the Breakpoint

Traverse from right to left and find the first index i such that:

nums[i] < nums[i + 1]

This is called the pivot.

If no such index exists, reverse the whole array.

Step 2: Find the Next Greater Element

Again traverse from right and find the first element greater than nums[i].

Swap them.

Step 3: Reverse the Right Part

Reverse the subarray from i+1 to end.

This ensures the next smallest lexicographical order.

Why This Works
We try to increase the number slightly.
Then rearrange the remaining elements in the smallest possible order.
This guarantees the immediate next permutation.
Time and Space Complexity

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

Implementation (Python)
class Solution:
def nextPermutation(self, nums):
n = len(nums)
i = n - 2

    # Step 1: Find pivot
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    # Step 2: If pivot exists, find element just greater than nums[i]
    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 suffix
    left = i + 1
    right = n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Dry Run Example

For:

[1,2,3]

Step 1:
Find pivot → 2 (because 2 < 3)

Step 2:
Swap 2 and 3 → [1,3,2]

Step 3:
Reverse after pivot (only one element)

Final result:

[1,3,2]
Special Case

For:

[3,2,1]

No pivot exists.
Reverse entire array:

[1,2,3]