Next Permutation

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

Time & Space Complexity