https://leetcode.com/problems/next-permutation

This problem is very similar to problem 556. Next Greater Element III, with exactly the same reasoning:

Imagine, that we have nums = [2, 3, 4, 1, 5, 7, 6, 4, 1] Then next permutation is [2, 3, 4, 1, 6, 1, 4, 5, 7]. Idea here is to start to look from the end and find decreasing pattern, like [7, 6, 4, 1] here, then look at previous element and insert it in correct place. For more details see https://leetcode.com/problems/next-greater-element-iii/discuss/983076/Python-O(m)-solution-explained.

Complexity: time complexity it is O(n), where n is length of nums. Space complexity is O(1) here, because we do everything in-place.

class Solution:
    def nextPermutation(self, nums):
        def reverse(L, start, end):
            while start < end:
                L[start], L[end] = L[end], L[start]
                start, end = start + 1, end - 1
        
        i, n = len(nums) - 1, len(nums)
        while i >= 1 and nums[i] <= nums[i-1]:
            i -= 1
            
        if i != 0:
            j = i
            while j + 1 < n and nums[j+1] > nums[i - 1]:
                j += 1
            
            nums[i-1], nums[j] = nums[j], nums[i-1]
        
        reverse(nums, i, n - 1)
        
        return nums

If you like the solution, you can upvote it on leetcode discussion section: Problem 0031