2026-09-21 — Next Permutation

Look at the array from the RIGHT. The longest suffix that is non-increasing is already as big as it can be — no change inside it can produce a "next" value. Find the first element just before that suffix that is smaller than the one to its right; that element must increase. Swap it with the SMALLEST element in the suffix that is still larger than it, then reverse the suffix.

def next_permutation(nums: list[int]) -> None:
    # 1. Find the longest non-increasing suffix; `i` is the pivot just
    #    before it (the last position where an increase is possible).
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    # 2. If the whole array is non-increasing, it is the last
    #    permutation: reverse everything to get the first one.
    if i >= 0:
        # 3. Swap the pivot with the smallest suffix element that is
        #    larger than it — because the suffix is descending, that is
        #    the LAST element with nums[j] > nums[i].
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]

    # 4. Make the suffix as small as possible: reverse it.
    left, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

How it works. A permutation's "value" is compared from the left, so to get the NEXT one you want to change the rightmost position you can, and make everything to its right as small as possible. The rightmost position you can increase is the pivot i found in step 1; the rest of the algorithm is bookkeeping around that swap.

Complexity. Time: O(n) — each pass (find pivot, find swap partner, reverse) touches each element at most once. Space: O(1) — only index variables.

Edge cases that matter. Single element (no change). Already the largest permutation (wrap around — the i >= 0 guard skips the swap and reverses the whole array). Duplicate values, e.g. [1, 1, 5] — the comparisons must be >= / <=, not > / <, or equal values are treated as changeable and the algorithm corrupts the input.

Common wrong answer. Swapping the pivot with the first suffix element that is larger (scanning left to right) instead of the smallest larger one. For [1, 5, 1] that picks the 5 in the wrong slot and yields an ordering that skips over the true next permutation. Because the suffix is descending, scanning from the RIGHT for the first element > nums[i] finds exactly the smallest larger one.