Next Permutation
Understanding the Problem
Given a sequence of numbers, rearrange them into the next sequence that would come after the current one if we listed all possible arrangements in dictionary order.
An odometer is a useful comparison. The number 1234 is followed by 1235, then 1236, and so on. When the last digit reaches its maximum, you increment the next digit and reset. Permutations work the same way, except instead of digits 0-9 you are working with the elements of the array, and instead of addition you are rearranging positions.
To get the next permutation, find the rightmost position where the sequence can still grow, make the smallest possible increase at that position, and arrange everything after it in the smallest possible order.
Key Constraints:
1 <= nums.length <= 100→ With n up to 100, the input is small. The difficulty is correctness, not raw speed.0 <= nums[i] <= 100→ Values can repeat, so the algorithm has to handle duplicates like[1, 1, 5]correctly.in place, constant extra memory→ We cannot copy the array or use extra data structures. This rules out the brute-force option of materializing all permutations and searching for the next one.
Approach 1: Generate All Permutations (Brute Force)
Intuition
Generate every possible permutation of the array, sort them in lexicographic order, find the current permutation in the list, and return the one after it. If the current permutation is the last in the list, wrap around to the first.
This is correct by construction, but impractical. For an array of length n there are n! permutations. With n = 10 that is 3.6 million arrangements to generate and sort, and with n = 20 it is over 2 quintillion. It also stores every permutation, so it violates the constant-memory requirement.
It does make the structure of the problem visible: when the permutations are listed in order, the transitions follow a fixed pattern that the next approach exploits directly.
Algorithm
- Generate all permutations of the input array.
- Sort the permutations in lexicographic order.
- Find the current array in the sorted list.
- Return the next permutation in the list (wrapping around to the first if needed).
Example Walkthrough
Input:
All permutations sorted: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]. Current is [1,2,3] at position 0. Next is position 1:
Code
- Time Complexity: O(n! n). Generating all permutations takes O(n!). Sorting them takes O(n! n log(n!)). Finding the current one takes O(n! * n).
- Space Complexity: O(n! * n). We store all n! permutations, each of length n.
This approach is simple but unusable for larger inputs. The next approach computes the next permutation directly from the current one, in place, without enumerating anything.
Approach 2: Optimal (Single Pass with Suffix Reversal)
Intuition
When the permutations of [1, 2, 3, 4] are listed in order, the rightmost elements change most frequently, like the least-significant digits of a number. When a suffix is already in descending order it cannot grow any larger, so the increase has to carry over to an earlier position.
That gives the algorithm: scan from the right to find the first position where the sequence can still grow (the pivot), swap the pivot with the smallest element to its right that is larger than it, and reverse the suffix to make it the smallest possible arrangement.
The pivot is found by scanning right to left while each element is greater than or equal to the one after it, so the entire suffix to the right of the pivot is in non-increasing order. That suffix is already the largest arrangement of those values, like the 99 in 1299, so no change confined to it can produce a larger permutation. The pivot is the leftmost position whose value can increase. Swapping it with the smallest suffix element that exceeds it makes the smallest legal increase at that position. After the swap the suffix is still non-increasing, so reversing it turns it into the smallest (ascending) arrangement, giving the next permutation overall.
Algorithm
- Start from the right end of the array. Find the first index
isuch thatnums[i] < nums[i + 1]. This is the pivot. - If no pivot exists (the array is in descending order), reverse the entire array and return.
- From the right end, find the first index
jsuch thatnums[j] > nums[i]. - Swap
nums[i]andnums[j]. - Reverse the subarray from
i + 1to the end.
Example Walkthrough
Code
- Time Complexity: O(n). Finding the pivot is at most O(n). Finding the successor is at most O(n). The swap is O(1). Reversing the suffix is at most O(n). In total, three passes through parts of the array.
- Space Complexity: O(1). Only a few integer variables. All modifications happen in-place.