Next Permutation — Solution

Problem

Given an array of integers, rearrange its elements into the next lexicographically greater permutation of those numbers. If no greater permutation exists (the array is fully descending), rearrange into the smallest possible order instead. The rearrangement must be done in place.

• Input: nums = [1, 2, 3]
• Output: [1, 3, 2]
• Explanation: [1, 3, 2] is the next permutation after [1, 2, 3] in lexicographic order.

Additional example:

• Input: nums = [3, 2, 1]
• Output: [1, 2, 3]
• Explanation: [3, 2, 1] is the largest permutation, so we wrap around to the smallest.

Intuition

Think of how you increment a number: you find the rightmost digit you can increase, increment it by the least amount possible, and set everything to its right as small as possible. The same logic applies here — scan from the right to find the first position where the value is smaller than what immediately follows it (the pivot), swap it with the smallest value to its right that still exceeds it, then reverse everything to the right of the pivot to make that suffix as small as possible.

Solution — Scan Right, Swap, Reverse

Find the rightmost position where the value drops below what follows it (the pivot), swap it with the rightmost element to its right that is still larger, then reverse the suffix to make it ascending.

1. Scan from right to left to find the rightmost pivot index where nums[pivot] < nums[pivot + 1]. If none exists, the array is the last permutation — reverse the whole array and return.
2. Scan from right to left to find the rightmost swap_pos where nums[swap_pos] > nums[pivot].
3. Swap nums[pivot] and nums[swap_pos].
4. Reverse the subarray from pivot + 1 to the end — this suffix is still in descending order after the swap, so reversing makes it ascending (the smallest possible arrangement).

1def nextPermutation(nums):
2    n = len(nums)
3    pivot = n - 2  # start just before the last element
4
5    # Find rightmost index where the sequence is still increasing from the right
6    while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
7        pivot -= 1
8
9    if pivot >= 0:  # valid pivot found — not the last permutation
10        # Find rightmost element that is strictly greater than the pivot value
11        swap_pos = n - 1
12        while nums[swap_pos] <= nums[pivot]:
13            swap_pos -= 1
14        nums[pivot], nums[swap_pos] = nums[swap_pos], nums[pivot]
15
16    # Reverse the suffix — it is descending after the swap, reversing gives the smallest order
17    left, right = pivot + 1, n - 1
18    while left < right:
19        nums[left], nums[right] = nums[right], nums[left]
20        left += 1
21        right -= 1

Time: O(n) — each of the three passes (find pivot, find swap target, reverse) touches at most n elements. Space: O(1) — all modifications happen in place with a constant number of index variables.

Complexity Summary

Common Mistakes

• Scanning from left instead of right for the pivot: The leftmost ascending pair is not the correct pivot — you need the rightmost one to make the smallest possible change to the permutation.
• Swapping with the leftmost valid j instead of the rightmost: The suffix after the pivot must remain in descending order after the swap so it can be reversed (not sorted). Swapping with any j that isn't rightmost breaks this invariant and would require an O(n log n) sort.
• Reversing from index pivot instead of pivot + 1: The pivot element has already been placed correctly by the swap; reversing from it would displace it again and corrupt the result.
• Not handling the fully-descending array: When no pivot exists (e.g., [3, 2, 1]), pivot ends at −1. The algorithm still produces the correct answer because reversing from pivot + 1 = 0 reverses the entire array into ascending order.
• Using > instead of >= in the pivot scan condition: The condition must be nums[pivot] >= nums[pivot + 1] (keep scanning while non-strictly-increasing) to correctly skip past equal elements and find the true rightmost pivot. Using > stops one element too early when duplicates are present.

Related Problems

• Permutations — generates all permutations of a set; next permutation steps through exactly this sequence one at a time
• Permutation Sequence — jumps directly to the kth permutation without iterating through all previous ones
• Permutation in String — uses the permutation concept in a sliding-window context to check for anagram containment
• Subsets — another combinatorial generation problem that builds intuition for lexicographic ordering of arrangements
• Next Greater Element II — finds the next greater value in a circular array, sharing the "scan right for the next ascending value" core pattern