List every way to order the values of nums, then sort those orderings like words in a dictionary: compare the first values, and on a tie the second, and so on. For [1, 2, 3] that gives [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. Equal values are interchangeable, so [1, 1, 2] has only three orderings: [1, 1, 2], [1, 2, 1], [2, 1, 1].
Write next_permutation(nums: list[int]) -> None that changes nums in place into the ordering that comes right after it in that list. If nums is already the last ordering (the values never go up), wrap around to the first one: the values in increasing order. Return nothing; the caller looks at nums.
nums = [2, 4, 3, 1]
next_permutation(nums)
nums # [3, 1, 2, 4]
nums = [6, 2, 9, 7, 7, 4]
next_permutation(nums)
nums # [6, 4, 2, 7, 7, 9]
nums = [5, 4, 2]
next_permutation(nums)
nums # [2, 4, 5] (it was the last ordering, so wrap around)
nums = [1, 3, 3]
next_permutation(nums)
nums # [3, 1, 3]
Constraints: 1 <= len(nums) <= 10^5; values are in [-10^9, 10^9] and may repeat. Listing every ordering is hopeless beyond about 10 values.
⭐ Bonus: checking each position by scanning everything to its right for a bigger value is O(n²) and still passes; a speed test on 10^5 values earns a star in O(n).
Show hint
the next ordering changes as little as possible at the front, so look at the end of the list first. What does the longest tail that never goes up tell you?