NEXT PERMUTATION

How I Understood Next Permutation
When I first saw this problem, it looked tricky because it asks to modify the array in-place and find the next lexicographical permutation.
But after breaking it down step by step, the solution became clear: find the pivot, swap, and reverse.

** Problem**
Given an array of numbers representing a permutation, you need to transform it into the next permutation in lexicographical order.
If the current permutation is the largest, you should rearrange it as the smallest (sorted ascending).

**Example:
**Python
nums = [1, 2, 3]

Next permutation: [1, 3, 2]

Python
nums = [3, 2, 1]

Next permutation: 1, 2, 3

*What I Noticed*
Instead of generating all permutations (which is inefficient), I focused on these key ideas:
Find the first decreasing element from the right (pivot)
Swap it with the smallest number larger than it to the right
Reverse the part of the array after the pivot
This ensures the next smallest lexicographical permutation.

What Helped Me
Breaking the problem into three clear steps made it manageable:
Find the pivot: the first number from the right that is smaller than its next number
Find the successor: the smallest number greater than the pivot to its right, and swap
Reverse the suffix: the numbers after the pivot to get the smallest order

** Code (Python)**
Python
from typing import List

class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Modify nums in-place to the next lexicographical permutation.
"""
n = len(nums)
pivot = -1

    # Step 1: Find the first decreasing element from the right
    for i in range(n - 2, -1, -1):
        if nums[i] < nums[i + 1]:
            pivot = i
            break

    # Step 2: If pivot exists, find successor and swap
    if pivot != -1:
        for j in range(n - 1, pivot, -1):
            if nums[j] > nums[pivot]:
                nums[pivot], nums[j] = nums[j], nums[pivot]
                break

    # Step 3: Reverse the elements after the pivot
    left, right = pivot + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

***Example Usage*
**Python
nums = [1, 2, 3]
solution = Solution()
solution.nextPermutation(nums)
print(nums)
Output:
Plain text
[1, 3, 2]

** Complexity**
Time: O(n) — iterate through the array at most twice
Space: O(1) — in-place modifications

** What I Learned**
This problem isn’t about complex logic.
It’s about:
Breaking the problem into simple, clear steps
Thinking about lexicographical order
Manipulating arrays in-place carefully
Once you understand pivot, swap, reverse, the solution is straightforward.

**** Final Thought****
At first, finding the next permutation seemed intimidating.
But once I asked myself:

** “Where does the order break from the right?”**
…it became intuitive.
This is a classic example of algorithmic thinking > brute force.