Next Permutation

Problem

Rearrange an array of integers into the next lexicographically greater permutation. If the array is already the largest permutation, rearrange it into the smallest one. The change must happen in place with constant extra memory.

Approach

Scan from the right for the first index i where nums[i] is smaller than nums[i + 1]. Everything to the right of i is in descending order, so that suffix is already as large as it can be.

If such an index exists, find the rightmost number in the suffix that is larger than nums[i] and swap the two. That makes the prefix grow by the smallest possible step.

Finally reverse the suffix. It was descending, so reversing it makes it ascending, the smallest arrangement of those numbers. When no index i exists, the whole array is reversed, which wraps around to the smallest permutation.

Solution

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Complexity

• Time: O(n).
• Space: O(1).

Edge cases

• A fully descending array wraps around to ascending order.
• Duplicates need the comparisons to use greater-or-equal, as above.
• A single element stays the same.