Next Permutation

#computerscience #python #algorithms #tutorial

Hi everyone!
This was one of the trickiest array problems I solved recently. At first, it felt confusing, but once I understood the pattern, it became much clearer.

Problem
Given an array, find the next lexicographically greater permutation.

If not possible, return the smallest permutation (sorted).

Example:
Input: [1, 2, 3]

Output: [1, 3, 2]

My Thought Process
Initially, I thought of generating all permutations — but that would be too slow.

Then I learned a smarter approach based on patterns in permutations.

Logic (Key Idea)

Traverse from right and find the first element where order breaks
Find a number just greater than it on the right
Swap them
Reverse the remaining part

Code (Python)

from typing import List
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
# Step 1: Find first decreasing element from right
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1

# Step 2: If found, find just larger element to swap
if i >= 0:
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]

# Step 3: Reverse the right part
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1