Next Permutation
Transform the array into the next lexicographically larger permutation.
Pattern fit
This is really a boundary and suffix-order problem: find the first descent from the right, swap with the next larger element, then reverse the suffix.
Key observation
The suffix after the pivot is descending, which is why the next larger element and final reversal can both be found efficiently.
Target complexity
O(n) / O(1)
How to break down the solution cleanly
This is really a boundary and suffix-order problem: find the first descent from the right, swap with the next larger element, then reverse the suffix.
The suffix after the pivot is descending, which is why the next larger element and final reversal can both be found efficiently.
Write down what each pointer means before you move them.
Use the current comparison to prove which side can be safely discarded.
Reference implementation
Python# Generic pattern template
# Opposite-direction pointers on a sorted array
left, right = 0, len(nums) - 1
while left < right:
if good(nums[left], nums[right]):
return answer
if should_move_left(nums[left], nums[right]):
left += 1
else:
right -= 1
# Fast/slow pointers
slow = 0
for fast in range(len(nums)):
if keep(nums[fast]):
nums[slow] = nums[fast]
slow += 1
Common pitfalls
Not handling the fully descending array case.
Sorting the suffix instead of reversing the already descending suffix.
Common follow-ups
Why is reversing enough after the swap?
How would you find the previous permutation?
Continue with related problems
Build repeatable depth inside the Two Pointers cluster before moving on.