Next Permutation

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

# Solution

Next Permutation animation

Complexity

time: O(n)O(n) (worst case: only two scans of the whole array are needed)
space: O(1)O(1) (all operations are in place)

def nextPermutation(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    # keep decrementing index until we found the pair a[i] and a[i−1] where a[i] > a[i−1]
    n = len(nums)
    i = n - 1
    while i >= 1 and nums[i-1] >= nums[i]:
        i -= 1
    if i >= 1:
        # find the smallest elt greater than nums[i-1]
        j = n - 1
        while nums[j] <= nums[i-1]:
            j -= 1
        # swap nums[i-1] and nums[j]
        nums[i-1], nums[j] = nums[j], nums[i-1]
    # reverse nums[i:]
    nums[i:] = nums[i:][::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18