DSA Patterns (Multi-Lang)•Part 2: Arrays, Strings & Hash Maps (6 - 18)
Next Permutation.
In Simple Words:
- Find rightmost pivot index $i$ where
nums[i] < nums[i+1]. - Find successor index $j$ from right where
nums[j] > nums[i]and swap them. - Reverse suffix after $i$ to get lexicographically smallest continuation.
- Time: $O(N)$ | Space: $O(1)$
Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++
Switch tabs or choose Alldef nextPermutation(nums: list[int]) -> None:
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:])