Next Permutation

Next Permutation
Problem Statement

Find the next lexicographically greater permutation of the array.
If not possible, return the smallest permutation (sorted).

Examples
[1,2,3] → [1,3,2]
[3,2,1] → [1,2,3]
[1,1,5] → [1,5,1]

Approach Explanation

To find the next permutation:

Steps

Traverse from right and find first decreasing element

Find the next greater element to the right

Swap them

Reverse the right part

Algorithm Steps

For array [1,2,3]:

Find break point → 2

Find next greater → 3

Swap → [1,3,2]

Reverse right side → Done

Python Code
nums = [1,2,3]

i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1

if i >= 0:
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]

nums[i+1:] = reversed(nums[i+1:])

print(nums)
Complexity
Type Complexity
Time O(n)
Space O(1)

Final Comparison
Problem Best Approach
Move Zeroes Two Pointer
Next Permutation Pivot + Swap + Reverse

Conclusion

These problems teach important array techniques:

Two pointer method

Swapping

Reversing

Lexicographical order

In-place operations

These are very common interview problems and help in understanding array manipulation efficiently.