Next Permutation

Intuition

Solution

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) <= 1:
            return

        if nums == list(sorted(nums, reverse=True)):
            nums.sort()
            return

        # Find the largest i where nums[i] < nums[i + 1]
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                break

        # Find the smallest j where j > i and nums[j] > nums[i]
        smallest_j = i + 1
        for j in range(i + 2, len(nums)):
            if nums[j] <= nums[i]:
                break
            if abs(nums[j] - nums[i]) < abs(nums[smallest_j] - nums[i]):
                smallest_j = j

        j = smallest_j
        # switch i, j
        nums[i], nums[j] = nums[j], nums[i]

        # Sort left part
        for num, k in zip(sorted(nums[i + 1:]), range(i + 1, len(nums))):
            nums[k] = num