Compute the next lexicographic permutation

Problem Statement

Given an array of integers nums, find the next lexicographically greater permutation of these numbers. If such an arrangement is impossible (i.e., the array is sorted in descending order), you must rearrange it to the lowest possible order (i.e., sorted in ascending order).

The operation must be done in-place, using only O(1) extra memory.

Function Signature

def next_permutation(nums: List[int]) -> None:
    """Do not return anything, modify nums in-place instead."""

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

Examples

Example 1: Input: nums = [1, 2, 3] Output: [1, 3, 2] Explanation: The next permutation after 123 is 132.

Example 2: Input: nums = [3, 2, 1] Output: [1, 2, 3] Explanation: Since the input is the largest permutation, we return the smallest possible arrangement.

Example 3: Input: nums = [1, 1, 5] Output: [1, 5, 1] Explanation: Handling duplicate values ensures the correct lexicographical jump.

Edge Cases

• Single element arrays.
• Arrays with all identical elements.
• Arrays already in descending order.