MediumNeetCode150ArrayTwo Pointers
Next Permutation
Find next lexicographically greater permutation.
Examples
Input
nums = [1,2,3]
Output
[1,3,2]
Next permutation of 123.
Constraints
- •
1 <= nums.length <= 100 - •
0 <= nums[i] <= 100
Approaches
Generate all permutations, find next.
CodeT: O(n! * n) | S: O(n! * n) output
Find first decreasing, swap, reverse.
CodeT: O(n) | S: O(1) in-place
def nextPermutation(nums):
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:])Same approach.
CodeT: O(n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Generate All | O(n! * n) | O(n! * n) output | Generate all permutations, find next. |
| One Pass from Right | O(n) | O(1) in-place | Find first decreasing, swap, reverse. |
| One Pass Optimized | O(n) | O(1) | Same approach. |
Generate All
T: O(n! * n)S: O(n! * n) output
Generate all permutations, find next.
One Pass from Right
T: O(n)S: O(1) in-place
Find first decreasing, swap, reverse.
One Pass Optimized
T: O(n)S: O(1)
Same approach.
Common Mistakes
Not handling all decreasing
Wrong swap index
Off-by-one in reverse