Next permutation in lexicographic order, in place

Rearrange an array of integers into the next permutation in lexicographic order. If the array is already the largest permutation, rearrange it into the smallest one (sorted ascending). Do it in place with constant extra memory.

Interface

Unless you agree on a different interface with the interviewer, assume:

• next_permutation(nums: list[int]) -> None — modifies nums in place.

Example

[1, 2, 3]  ->  [1, 3, 2]
[1, 3, 2]  ->  [2, 1, 3]
[2, 3, 1]  ->  [3, 1, 2]
[3, 2, 1]  ->  [1, 2, 3]     # last permutation wraps around
[1, 1, 5]  ->  [1, 5, 1]     # duplicates allowed

Constraints

• 1 <= len(nums) <= 100.
• 0 <= nums[i] <= 100; values may repeat.

Clarifying questions

• Can the array contain duplicates?
• Should the last permutation wrap around, or report that there is no next one?
• Must it be in place?

What a strong answer covers

• Find the pivot: the rightmost index i with nums[i] < nums[i + 1]. Everything after it is non-increasing.
• If there is no pivot, reverse the whole array.
• Otherwise swap nums[i] with the rightmost element greater than it, then reverse the suffix after i.
• Why this gives the next permutation and not a later one; strict comparisons so duplicates work.
• O(n) time, O(1) extra space.
• Tests: one element, two elements, all equal, the last permutation, duplicates.

Follow-ups

• Return the previous permutation instead.
• Return the k-th permutation of 1..n directly, without stepping through all of them.
• Find the smallest number larger than a given integer that uses the same digits, or -1 if none fits in 32 bits.