Leetcode 31. Next Permutation

Let's understand what we're being asked to do. We have an array like [1, 2, 3] and need to rearrange it to the next lexicographically greater permutation.

Tracing through: [1, 2, 3] becomes [1, 3, 2] (next greater). Then [1, 3, 2] becomes [2, 1, 3] (next greater). Eventually [3, 2, 1] is the largest permutation, so it wraps around to [1, 2, 3] (smallest).

Important constraint: We must rearrange in-place using only O(1) extra space. We can't create a new array!

Edge cases to consider: What if the array is already the largest permutation like [3, 2, 1]? (wrap to smallest: [1, 2, 3]). What if all elements are the same like [1, 1, 1]? (no change). What if the array has only one element?

To find the next permutation, we need to find the rightmost position where we can make a swap that increases the value.

Look from right to left: find the first element that is smaller than its right neighbor. This is the 'pivot' - the position where we can increase the value. Everything to the right of this pivot is in descending order (that's why we couldn't find a swap earlier).

Once we find the pivot, we need to swap it with the smallest element to its right that is larger than it. This gives us the minimal increase.

But we're not done! After the swap, the elements to the right of the pivot are still in descending order. To get the next permutation (not just any larger one), we must reverse this suffix to make it ascending (the smallest arrangement).

Think about counting: to go from 1234 to the next number, you increment the rightmost digit: 1235. But what about 1239? You can't just increment the 9.

Instead, you find the rightmost digit you can increment (the 3), increment it to 4, and reset everything to its right to the smallest values: 1240. The same logic applies to permutations - find where you can 'increment', do the minimal increment, then reset the suffix to its smallest arrangement.

The optimal approach works in three steps: (1) Find the rightmost 'pivot' - the first element from the right that is smaller than its right neighbor. If no such element exists, the array is the largest permutation. (2) Find the smallest element to the right of the pivot that is larger than the pivot, and swap them. (3) Reverse the suffix after the pivot position to get the smallest arrangement. This gives us the next lexicographically greater permutation in-place with O(1) space.

def next_permutation(nums):
    """
    Rearrange array to next lexicographically greater permutation in-place.
    If no larger permutation exists, rearrange to smallest (ascending) order.
    """
    n = len(nums)
    
    # Step 1: Find the rightmost pivot (first element from right smaller than its right neighbor)
    pivot = -1
    for i in range(n - 2, -1, -1):
        if nums[i] < nums[i + 1]:
            pivot = i
            break
    
    # If no pivot found, array is largest permutation - reverse entire array
    if pivot == -1:
        nums.reverse()
        return nums
    
    # Step 2: Find smallest element to right of pivot that is larger than pivot
    successor = -1
    for i in range(n - 1, pivot, -1):
        if nums[i] > nums[pivot]:
            successor = i
            break
    
    # Swap pivot with successor
    nums[pivot], nums[successor] = nums[successor], nums[pivot]
    
    # Step 3: Reverse the suffix after pivot to get smallest arrangement
    left = pivot + 1
    right = n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    
    return nums

• Two-pointer pivot identification: The next permutation algorithm starts by scanning from right-to-left to find the first pivot element (arr[i] < arr[i+1]) - this rightmost ascending pair marks where the permutation can be increased, since everything to its right is already in descending order (the largest possible arrangement).
• Reverse for minimal increment: After swapping the pivot with its successor, reverse the suffix (everything after the pivot position) rather than sorting it - this works because the suffix is already in descending order, and reversing transforms it to ascending order (the smallest arrangement), ensuring the next permutation is the immediate successor.
• In-place array manipulation mastery: Achieve O(1) space by using three distinct operations on the same array: (1) right-to-left scan to find pivot, (2) right-to-left scan to find swap candidate, (3) two-pointer reversal of suffix - no auxiliary data structures needed.
• Edge case: descending array handling: When no pivot exists (array is completely descending like [3,2,1]), the entire array IS the suffix to reverse - this naturally wraps around to the smallest permutation [1,2,3], elegantly handling the circular boundary condition without special logic.
• Greedy successor selection: When finding the element to swap with the pivot, scan from the right to find the smallest element that's still larger than the pivot - this greedy choice ensures we increment the permutation by the minimum amount necessary for the next lexicographic order.
• Permutation generation pattern: This algorithm is the foundation for iterative permutation enumeration - repeatedly applying next permutation generates all n! permutations in sorted order, useful for combinatorial problems, testing frameworks, and scenarios where recursive backtracking is too memory-intensive.