Next Permutation – Solution & Complexity

Q: What is the time and space complexity of Next Permutation?

The optimal Next Permutation solution runs in `O(n)` time and `O(1)` space. Scan from the right to find the pivot, swap with the next-larger suffix value, then reverse the descending suffix.

Q: What is the most efficient way to solve Next Permutation?

Scan from the right to find the pivot, swap with the next-larger suffix value, then reverse the descending suffix. This gives `O(n)` time complexity, and is a classic arrays, two pointers, and greedy problem.

Q: How do you solve Next Permutation in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Next Permutation solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Next Permutation an easy or hard interview question?

Next Permutation is generally rated **Medium**. It tests arrays, two pointers, and greedy, which are common coding-interview patterns.

Solution Walkthrough

1. Understand the lexicographic rule

A permutation is "next" only if it is larger than the current one but as small as possible among all larger permutations.
That means we must change the array as far to the right as possible, then keep the suffix minimal.

2. Brute-force by rebuilding the suffix

Scan pivot positions from right to left.
For the first pivot that has a larger value somewhere to its right, swap in the smallest larger value and then sort the suffix.
This is correct, but the explicit suffix sort costs extra work.

def next_permutation(nums: list[int]) -> list[int]:
    arr = nums[:]
    for pivot in range(len(arr) - 2, -1, -1):
        larger = [value for value in arr[pivot + 1:] if value > arr[pivot]]
        if not larger:
            continue
        swap_value = min(larger)
        swap_index = len(arr) - 1
        while arr[swap_index] != swap_value:
            swap_index -= 1
        arr[pivot], arr[swap_index] = arr[swap_index], arr[pivot]
        arr[pivot + 1:] = sorted(arr[pivot + 1:])
        return arr
    return sorted(arr)

3. Exploit the descending suffix

The first index from the right where nums[i] < nums[i + 1] is the pivot.
Everything to its right is already in descending order, so once we swap in the next-larger value, reversing that suffix makes it as small as possible.

4. Build the optimal O(n) transformation

Find the pivot from the right.
Find the first value from the right that is larger than the pivot and swap them.
Reverse the suffix in place instead of sorting it.

def next_permutation(nums: list[int]) -> list[int]:
    arr = nums[:]
    pivot = len(arr) - 2
    while pivot >= 0 and arr[pivot] >= arr[pivot + 1]:
        pivot -= 1
    if pivot >= 0:
        swap_index = len(arr) - 1
        while arr[swap_index] <= arr[pivot]:
            swap_index -= 1
        arr[pivot], arr[swap_index] = arr[swap_index], arr[pivot]
    arr[pivot + 1:] = reversed(arr[pivot + 1:])
    return arr

5. Dry run / state trace

Trace nums = [1,2,3,6,5,4].

step	state	explanation
find pivot	`[1,2,3,6,5,4]`	scan from the right; `3 < 6`, so pivot index is `2`
find swap	`[1,2,3,6,5,4]`	the first value from the right larger than `3` is `4`
swap	`[1,2,4,6,5,3]`	now the prefix is the next-larger prefix
reverse suffix	`[1,2,4,3,5,6]`	the suffix was descending, so reversing it makes it minimal

6. Common mistakes and follow-ups

Sorting the whole array after the swap, which is correct but slower than necessary.
Picking a larger suffix value that is not the smallest possible larger value.
Forgetting the "already highest permutation" case, which should wrap to ascending order.
Follow-up: how would you do the in-place mutation-only LeetCode version if the function returned void?

7. Edge cases to test mentally

Single-element arrays stay unchanged.
Arrays with all equal values also stay unchanged.
A fully descending array should wrap to ascending order.
Duplicates in the suffix still work because we swap with the rightmost value that is just large enough.

8. Final full solution and complexity

Find the pivot, swap with the next-larger value from the right, then reverse the descending suffix. This runs in O(n) time and uses O(n) output space here only because we return a new array rather than mutating the caller-owned one.

def next_permutation(nums: list[int]) -> list[int]:
    arr = nums[:]
    pivot = len(arr) - 2
    while pivot >= 0 and arr[pivot] >= arr[pivot + 1]:
        pivot -= 1

    if pivot >= 0:
        swap_index = len(arr) - 1
        while arr[swap_index] <= arr[pivot]:
            swap_index -= 1
        arr[pivot], arr[swap_index] = arr[swap_index], arr[pivot]

    arr[pivot + 1:] = reversed(arr[pivot + 1:])
    return arr

Next Permutation – Solution & Complexity

Solution Walkthrough

1. Understand the lexicographic rule

2. Brute-force by rebuilding the suffix

3. Exploit the descending suffix

4. Build the optimal O(n) transformation

5. Dry run / state trace

6. Common mistakes and follow-ups

7. Edge cases to test mentally

8. Final full solution and complexity

FAQ

What is the time and space complexity of Next Permutation?

What is the most efficient way to solve Next Permutation?

How do you solve Next Permutation in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Next Permutation an easy or hard interview question?

See also