Builds on Converging Pointers, which you haven’t finished yet.
Next Lexicographic Permutation (Narayana Pandita's Algorithm, std::next_permutation)
Next Permutation (LC 31)(opens leetcode.com)
Write out every ordering of the values in nums and sort those orderings the way a dictionary sorts words: compare the first values, and on a tie the next ones, and so on. For nums = [1,2,3] that list is [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The next permutation of nums is the ordering that comes right after it in the list. When nums is already the last ordering, nothing comes after it, and the answer is the first ordering instead: the values in ascending order.
Change nums into its next permutation in place: move its values around inside the array itself, with only a fixed amount of extra memory. Equal values make fewer distinct orderings: [1,1,5] has only [1,1,5], [1,5,1] and [5,1,1].
[3] cannot grow on its own, and 2 < 3, so index 1 is the pivot. The only larger value after it is 3: the swap gives [1,3,2], and a one-value tail stays as it is.Next Permutation
digits ➔ pivot, swap, reverse suffix ➔ next permutation| 1 | def next_permutation(nums: list[int]) -> None: |
| 2 | """Next Permutation: grow the rightmost position that can grow, by the smallest step, then reset the tail. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | # 1. Find The Pivot, The Rightmost Position That Can Grow: |
| 6 | # The tail nums[i + 1:] never increases, so it is already the largest order of its own values; walking i left stops at the first break in that run, which is the rightmost position that can still grow. |
| 7 | i = len(nums) - 2 |
| 8 | while i >= 0 and nums[i] >= nums[i + 1]: |
| 9 | i -= 1 |
| 10 | |
| 11 | if i >= 0: |
| 12 | # 2. Grow The Pivot By The Smallest Step: |
| 13 | # The tail never increases, so scanning j from the right, the first value strictly larger than nums[i] (<= skips equal values too) is the smallest value that can replace it. |
| 14 | j = len(nums) - 1 |
| 15 | while nums[j] <= nums[i]: |
| 16 | j -= 1 |
| 17 | nums[i], nums[j] = nums[j], nums[i] |
| 18 | |
| 19 | # 3. Reset The Tail To Its Smallest Order: |
| 20 | # The tail still never increases after the swap, so reversing it puts it in ascending order, its smallest possible arrangement; when no pivot exists, this reverses the whole array into its first arrangement. |
| 21 | left, right = i + 1, len(nums) - 1 |
| 22 | while left < right: |
| 23 | nums[left], nums[right] = nums[right], nums[left] |
| 24 | left += 1 |
| 25 | right -= 1 |
nums[i + 1:] never increases from left to right, and it still never increases after the swap, so reversing it gives the smallest order of those values.The next arrangement changes as little as possible, and only at the right end. Walk i left from the end while nums[i] >= nums[i + 1]: that tail never increases, so it is already the largest order of its values and nothing inside it can grow. The first i with nums[i] < nums[i + 1] is the pivot, the rightmost position that can grow. Grow it by the smallest step: walk j left from the end past every value <= nums[i], swap nums[i] with nums[j] (the smallest value in the tail that is larger), then reverse the tail, which turns its largest order into its smallest. This is correct because every arrangement between the old one and the new one would have to keep nums[:i] and put a value at i that is larger than nums[i] but smaller than nums[j], and the tail holds no such value. When there is no pivot, i ends at -1, the whole array is the last arrangement, and reversing from index 0 wraps it to the first one. The trap is repeated values: both scans must also skip equal values, nums[i] >= nums[i + 1] and nums[j] <= nums[i]. With nums[j] < nums[i], [1,5,1] swaps its two 1s and ends as [1,1,5], a step backwards instead of [5,1,1].
See it run
Next Permutation, nums = [1, 2, 5, 3, 3, 2]
i 4j not set
Each cell is one item of nums. The tags under the cells show the pointers.
ithe position the pivot scan is testingi + 1the item after i, compared with nums[i]pivotthe rightmost position that can growjthe position of the value that is swapped with the pivottailthe items after the pivot, which never increaseleftthe left pointer of the tail reversalrightthe right pointer of the tail reversal
Find the pivot first. i starts at len(nums) - 2 = 4.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing
nums[j] < nums[i]in the swap scanMistakewhile nums[j] < nums[i]:Fixwhile nums[j] <= nums[i]:What happens: The swap needs the smallest value in the tail that is larger than
nums[i]. An equal value is not larger. With<, the scan stops on a value equal to the pivot. Swapping two equal values changes nothing. Reversing the tail then gives a smaller arrangement, a step backwards.Example: nums = [1, 5, 1]Mistake: returns [1, 1, 5]Fix: returns [5, 1, 1]
- The input is a rank
k, not an arrangement to step from, as in Permutation Sequence (LC 60): you must land on thek-th arrangement directly, and steppingk - 1times costs up ton!steps. See Count and Skip - You must return every distinct arrangement, as in Permutations II (LC 47), not the single one after a given arrangement. See Permutations
- Digits are deleted to make the smallest number and the ones that stay keep their order, as in Remove K Digits (LC 402): nothing is rearranged. See Lexicographic Stack
Deep Dive
Why the pivot is the rightmost position that can grow
Permutations are ordered like words in a dictionary: compare the first position, then the second, and so on. The next permutation is the smallest arrangement that is larger than the current one. To be the smallest, it must keep as long a prefix of the current arrangement as it can.
A tail that never increases from left to right, such as 5, 3, 3, 2, is already the largest arrangement of its own values. Rearranging only inside such a tail can never give a larger arrangement. So the prefix before the tail cannot be kept in full, and the change must reach the position just before the tail.
That position is the pivot. The scan while i >= 0 and nums[i] >= nums[i + 1] walks i left from len(nums) - 2 and stops at the first nums[i] < nums[i + 1]. For nums = [1, 2, 5, 3, 3, 2] the scan checks i = 4, i = 3 and i = 2, and stops at i = 1, because 2 < 5. The pivot is nums[1] = 2 and the tail is 5, 3, 3, 2.
The pivot is the rightmost position that can grow. Everything to its right never increases. So nums[:1] = [1] is kept, and the value at position 1 must become larger than 2.
Why swap with the smallest larger value, then reverse the tail
The new value at the pivot must be larger than nums[i], and it should be as small as possible. The tail never increases, so scanning j from the right finds the smallest tail value that is larger than nums[i] first. For the example, j starts at 5. nums[5] = 2 is not larger than the pivot 2, so j moves to 4. nums[4] = 3 is larger, so j = 4. After the swap, nums = [1, 3, 5, 3, 2, 2].
The tail 5, 3, 2, 2 still never increases after the swap. Here is why. j is the rightmost value larger than nums[i], so every value to the right of j is at most the old pivot, and the old pivot is now at position j. The value at j - 1, if it is still in the tail, was at least the old nums[j], which is larger than the old pivot. So the order does not break on either side of j.
A tail that never increases is its largest arrangement, and its smallest arrangement is the same values in increasing order. Reversing a tail that never increases gives exactly that. left, right = i + 1, len(nums) - 1 walk inward and swap. The tail 5, 3, 2, 2 becomes 2, 2, 3, 5, and nums = [1, 3, 2, 2, 3, 5].
The three steps together give the smallest arrangement that is larger than the original. The prefix [1] is kept, the pivot position gets the smallest larger value, and the tail is as small as it can be.
Repeated values and the last arrangement
Both scans must skip equal values. The board shows both places. In the pivot scan, nums[3] = nums[4] = 3. With > instead of >=, the scan would stop at i = 3 and take 3 as the pivot. Then the j scan would walk left past positions 5, 4 and 3 and stop at the 5 at position 2. The swap and the reversal give [1, 2, 3, 5, 2, 3], which is smaller than the input.
In the swap scan, nums[5] = 2 equals the pivot. With < instead of <=, the scan would stop at j = 5 and swap two equal values. The tail reversal would then give [1, 2, 2, 3, 3, 5], which is also smaller than the input. The next permutation must be larger, so equal values must be skipped.
When no pivot exists, the scan ends with i = -1. The whole array never increases, so it is the last arrangement. The next one wraps around to the first, the sorted order. The reversal runs from left = 0, and [3, 2, 1] becomes [1, 2, 3]. Next Permutation (LC 31) asks for this wrap-around.
The other examples of Next Permutation (LC 31) follow the same steps. [1, 2, 3] has pivot 2, swaps with 3 and gives [1, 3, 2]. [1, 1, 5] has pivot 1 at position 1, swaps with 5 and gives [1, 5, 1].
Cost and where else it is used
Each of the three scans moves a pointer at most N positions, and all changes happen inside nums. So the time is O(N) and the space is O(1). Listing the arrangements and choosing the next would take O(N * N!).
Next Greater Element III (LC 556) runs the same steps on the digits of a number. It never wraps around: no pivot means the answer is -1, and an answer above 2^31 - 1 is also -1.
Permutation Sequence (LC 60) gives a rank k instead of an arrangement. Stepping k - 1 times with this card would take up to N! steps, so that problem finds the digits directly.
Previous Permutation With One Swap (LC 1053) scans from the right in the same way, with the comparisons reversed. It makes one swap and does not reverse a tail.
60-Second Pitch
"The next permutation changes as little as possible, and only at the right end. I walk i left from the end while nums[i] >= nums[i + 1]. That tail never increases, so it is already its largest arrangement. The first i with nums[i] < nums[i + 1] is the pivot. I scan j from the right past every value <= nums[i], and swap nums[i] with nums[j]. That is the smallest larger value. Both scans skip equal values. The tail still never increases after the swap, so I reverse it with two pointers. That gives its smallest order. If there is no pivot, the reversal covers the whole array and wraps to the first arrangement. The time is O(N) and the space is O(1)."
Common Questions
- What is the time and space complexity?
O(N)time, because the pivot scan, the swap scan and the reversal each touch at most N items.O(1)extra space, because everything happens insidenums.- Why does the tail never increase when the scan stops?
The scan only moves left past positions where
nums[i] >= nums[i + 1]. Each of those steps extends a run that does not increase. The run ends at the first position where the order goes up.- Why reverse the tail instead of sorting it?
The tail never increases after the swap, so reversing it gives increasing order. That is the sorted order, in
O(N)time. Sorting would give the same result with more work.- How do you handle repeated values?
Use
>=in the pivot scan and<=in the swap scan. Equal values must be skipped in both. With[1, 5, 1], the right answer is[5, 1, 1], and<in the swap scan gives[1, 1, 5].- How would you get the previous permutation, or the k-th one?
The previous permutation is the mirror: find the rightmost position where the order drops, and use the opposite comparisons. For the k-th permutation, as in Permutation Sequence (LC 60), compute the digits directly with factorials. Stepping k - 1 times would cost too much.
SWE Reasoning
Spot it
- The statement asks for the next arrangement in dictionary order, in place (Next Permutation (LC 31)).
- The statement asks for the next larger number that uses the same digits (Next Greater Element III (LC 556)).
- Listing all arrangements is too slow, and the answer is only one step away from the input.
The invariant, step by step
istarts atlen(nums) - 2. The tailnums[i + 1:]has one item, so it never increases.- While
nums[i] >= nums[i + 1], the tail starting atialso never increases, soimoves left. - The loop stops at the first
nums[i] < nums[i + 1]. Thatiis the pivot, and the tail after it never increases. - The scan from
j = len(nums) - 1skips every value<= nums[i]and stops at the smallest tail value that is larger. - The swap puts that value at the pivot. The tail still never increases.
- Reversing the tail puts its values in increasing order, which is their smallest arrangement. With
i = -1, this reverses the whole array.
Traps
nums[j] < nums[i]in the swap scan. The scan stops on a value equal to the pivot. For[1, 5, 1], the result is[1, 1, 5]instead of[5, 1, 1].nums[i] > nums[i + 1]in the pivot scan. The scan stops on two equal values. For[1, 5, 5], thejscan runs past the front and Python raises an IndexError.- Returning early when there is no pivot.
[3, 2, 1]must become[1, 2, 3]. Reversing from index 0 does that. - Sorting the tail instead of reversing it. The answer is the same, but sorting costs
O(N log N)and the reversal costsO(N). - Using this card for a rank. If the statement gives
kand asks for thek-th arrangement, compute it directly.
Practice
Builds on Converging Pointers, which you haven’t finished yet.
Next Lexicographic Permutation (Narayana Pandita's Algorithm, std::next_permutation)
Next Permutation (LC 31)(opens leetcode.com)
Write out every ordering of the values in nums and sort those orderings the way a dictionary sorts words: compare the first values, and on a tie the next ones, and so on. For nums = [1,2,3] that list is [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The next permutation of nums is the ordering that comes right after it in the list. When nums is already the last ordering, nothing comes after it, and the answer is the first ordering instead: the values in ascending order.
Change nums into its next permutation in place: move its values around inside the array itself, with only a fixed amount of extra memory. Equal values make fewer distinct orderings: [1,1,5] has only [1,1,5], [1,5,1] and [5,1,1].
[3] cannot grow on its own, and 2 < 3, so index 1 is the pivot. The only larger value after it is 3: the swap gives [1,3,2], and a one-value tail stays as it is.Next Permutation
digits ➔ pivot, swap, reverse suffix ➔ next permutation| 1 | def next_permutation(nums: list[int]) -> None: |
| 2 | """Next Permutation: grow the rightmost position that can grow, by the smallest step, then reset the tail. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | # 1. Find The Pivot, The Rightmost Position That Can Grow: |
| 6 | # The tail nums[i + 1:] never increases, so it is already the largest order of its own values; walking i left stops at the first break in that run, which is the rightmost position that can still grow. |
| 7 | i = len(nums) - 2 |
| 8 | while i >= 0 and nums[i] >= nums[i + 1]: |
| 9 | i -= 1 |
| 10 | |
| 11 | if i >= 0: |
| 12 | # 2. Grow The Pivot By The Smallest Step: |
| 13 | # The tail never increases, so scanning j from the right, the first value strictly larger than nums[i] (<= skips equal values too) is the smallest value that can replace it. |
| 14 | j = len(nums) - 1 |
| 15 | while nums[j] <= nums[i]: |
| 16 | j -= 1 |
| 17 | nums[i], nums[j] = nums[j], nums[i] |
| 18 | |
| 19 | # 3. Reset The Tail To Its Smallest Order: |
| 20 | # The tail still never increases after the swap, so reversing it puts it in ascending order, its smallest possible arrangement; when no pivot exists, this reverses the whole array into its first arrangement. |
| 21 | left, right = i + 1, len(nums) - 1 |
| 22 | while left < right: |
| 23 | nums[left], nums[right] = nums[right], nums[left] |
| 24 | left += 1 |
| 25 | right -= 1 |
nums[i + 1:] never increases from left to right, and it still never increases after the swap, so reversing it gives the smallest order of those values.The next arrangement changes as little as possible, and only at the right end. Walk i left from the end while nums[i] >= nums[i + 1]: that tail never increases, so it is already the largest order of its values and nothing inside it can grow. The first i with nums[i] < nums[i + 1] is the pivot, the rightmost position that can grow. Grow it by the smallest step: walk j left from the end past every value <= nums[i], swap nums[i] with nums[j] (the smallest value in the tail that is larger), then reverse the tail, which turns its largest order into its smallest. This is correct because every arrangement between the old one and the new one would have to keep nums[:i] and put a value at i that is larger than nums[i] but smaller than nums[j], and the tail holds no such value. When there is no pivot, i ends at -1, the whole array is the last arrangement, and reversing from index 0 wraps it to the first one. The trap is repeated values: both scans must also skip equal values, nums[i] >= nums[i + 1] and nums[j] <= nums[i]. With nums[j] < nums[i], [1,5,1] swaps its two 1s and ends as [1,1,5], a step backwards instead of [5,1,1].
See it run
Next Permutation, nums = [1, 2, 5, 3, 3, 2]
i 4j not set
Each cell is one item of nums. The tags under the cells show the pointers.
ithe position the pivot scan is testingi + 1the item after i, compared with nums[i]pivotthe rightmost position that can growjthe position of the value that is swapped with the pivottailthe items after the pivot, which never increaseleftthe left pointer of the tail reversalrightthe right pointer of the tail reversal
Find the pivot first. i starts at len(nums) - 2 = 4.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing
nums[j] < nums[i]in the swap scanMistakewhile nums[j] < nums[i]:Fixwhile nums[j] <= nums[i]:What happens: The swap needs the smallest value in the tail that is larger than
nums[i]. An equal value is not larger. With<, the scan stops on a value equal to the pivot. Swapping two equal values changes nothing. Reversing the tail then gives a smaller arrangement, a step backwards.Example: nums = [1, 5, 1]Mistake: returns [1, 1, 5]Fix: returns [5, 1, 1]
- The input is a rank
k, not an arrangement to step from, as in Permutation Sequence (LC 60): you must land on thek-th arrangement directly, and steppingk - 1times costs up ton!steps. See Count and Skip - You must return every distinct arrangement, as in Permutations II (LC 47), not the single one after a given arrangement. See Permutations
- Digits are deleted to make the smallest number and the ones that stay keep their order, as in Remove K Digits (LC 402): nothing is rearranged. See Lexicographic Stack
Deep Dive
Why the pivot is the rightmost position that can grow
Permutations are ordered like words in a dictionary: compare the first position, then the second, and so on. The next permutation is the smallest arrangement that is larger than the current one. To be the smallest, it must keep as long a prefix of the current arrangement as it can.
A tail that never increases from left to right, such as 5, 3, 3, 2, is already the largest arrangement of its own values. Rearranging only inside such a tail can never give a larger arrangement. So the prefix before the tail cannot be kept in full, and the change must reach the position just before the tail.
That position is the pivot. The scan while i >= 0 and nums[i] >= nums[i + 1] walks i left from len(nums) - 2 and stops at the first nums[i] < nums[i + 1]. For nums = [1, 2, 5, 3, 3, 2] the scan checks i = 4, i = 3 and i = 2, and stops at i = 1, because 2 < 5. The pivot is nums[1] = 2 and the tail is 5, 3, 3, 2.
The pivot is the rightmost position that can grow. Everything to its right never increases. So nums[:1] = [1] is kept, and the value at position 1 must become larger than 2.
Why swap with the smallest larger value, then reverse the tail
The new value at the pivot must be larger than nums[i], and it should be as small as possible. The tail never increases, so scanning j from the right finds the smallest tail value that is larger than nums[i] first. For the example, j starts at 5. nums[5] = 2 is not larger than the pivot 2, so j moves to 4. nums[4] = 3 is larger, so j = 4. After the swap, nums = [1, 3, 5, 3, 2, 2].
The tail 5, 3, 2, 2 still never increases after the swap. Here is why. j is the rightmost value larger than nums[i], so every value to the right of j is at most the old pivot, and the old pivot is now at position j. The value at j - 1, if it is still in the tail, was at least the old nums[j], which is larger than the old pivot. So the order does not break on either side of j.
A tail that never increases is its largest arrangement, and its smallest arrangement is the same values in increasing order. Reversing a tail that never increases gives exactly that. left, right = i + 1, len(nums) - 1 walk inward and swap. The tail 5, 3, 2, 2 becomes 2, 2, 3, 5, and nums = [1, 3, 2, 2, 3, 5].
The three steps together give the smallest arrangement that is larger than the original. The prefix [1] is kept, the pivot position gets the smallest larger value, and the tail is as small as it can be.
Repeated values and the last arrangement
Both scans must skip equal values. The board shows both places. In the pivot scan, nums[3] = nums[4] = 3. With > instead of >=, the scan would stop at i = 3 and take 3 as the pivot. Then the j scan would walk left past positions 5, 4 and 3 and stop at the 5 at position 2. The swap and the reversal give [1, 2, 3, 5, 2, 3], which is smaller than the input.
In the swap scan, nums[5] = 2 equals the pivot. With < instead of <=, the scan would stop at j = 5 and swap two equal values. The tail reversal would then give [1, 2, 2, 3, 3, 5], which is also smaller than the input. The next permutation must be larger, so equal values must be skipped.
When no pivot exists, the scan ends with i = -1. The whole array never increases, so it is the last arrangement. The next one wraps around to the first, the sorted order. The reversal runs from left = 0, and [3, 2, 1] becomes [1, 2, 3]. Next Permutation (LC 31) asks for this wrap-around.
The other examples of Next Permutation (LC 31) follow the same steps. [1, 2, 3] has pivot 2, swaps with 3 and gives [1, 3, 2]. [1, 1, 5] has pivot 1 at position 1, swaps with 5 and gives [1, 5, 1].
Cost and where else it is used
Each of the three scans moves a pointer at most N positions, and all changes happen inside nums. So the time is O(N) and the space is O(1). Listing the arrangements and choosing the next would take O(N * N!).
Next Greater Element III (LC 556) runs the same steps on the digits of a number. It never wraps around: no pivot means the answer is -1, and an answer above 2^31 - 1 is also -1.
Permutation Sequence (LC 60) gives a rank k instead of an arrangement. Stepping k - 1 times with this card would take up to N! steps, so that problem finds the digits directly.
Previous Permutation With One Swap (LC 1053) scans from the right in the same way, with the comparisons reversed. It makes one swap and does not reverse a tail.
60-Second Pitch
"The next permutation changes as little as possible, and only at the right end. I walk i left from the end while nums[i] >= nums[i + 1]. That tail never increases, so it is already its largest arrangement. The first i with nums[i] < nums[i + 1] is the pivot. I scan j from the right past every value <= nums[i], and swap nums[i] with nums[j]. That is the smallest larger value. Both scans skip equal values. The tail still never increases after the swap, so I reverse it with two pointers. That gives its smallest order. If there is no pivot, the reversal covers the whole array and wraps to the first arrangement. The time is O(N) and the space is O(1)."
Common Questions
- What is the time and space complexity?
O(N)time, because the pivot scan, the swap scan and the reversal each touch at most N items.O(1)extra space, because everything happens insidenums.- Why does the tail never increase when the scan stops?
The scan only moves left past positions where
nums[i] >= nums[i + 1]. Each of those steps extends a run that does not increase. The run ends at the first position where the order goes up.- Why reverse the tail instead of sorting it?
The tail never increases after the swap, so reversing it gives increasing order. That is the sorted order, in
O(N)time. Sorting would give the same result with more work.- How do you handle repeated values?
Use
>=in the pivot scan and<=in the swap scan. Equal values must be skipped in both. With[1, 5, 1], the right answer is[5, 1, 1], and<in the swap scan gives[1, 1, 5].- How would you get the previous permutation, or the k-th one?
The previous permutation is the mirror: find the rightmost position where the order drops, and use the opposite comparisons. For the k-th permutation, as in Permutation Sequence (LC 60), compute the digits directly with factorials. Stepping k - 1 times would cost too much.
SWE Reasoning
Spot it
- The statement asks for the next arrangement in dictionary order, in place (Next Permutation (LC 31)).
- The statement asks for the next larger number that uses the same digits (Next Greater Element III (LC 556)).
- Listing all arrangements is too slow, and the answer is only one step away from the input.
The invariant, step by step
istarts atlen(nums) - 2. The tailnums[i + 1:]has one item, so it never increases.- While
nums[i] >= nums[i + 1], the tail starting atialso never increases, soimoves left. - The loop stops at the first
nums[i] < nums[i + 1]. Thatiis the pivot, and the tail after it never increases. - The scan from
j = len(nums) - 1skips every value<= nums[i]and stops at the smallest tail value that is larger. - The swap puts that value at the pivot. The tail still never increases.
- Reversing the tail puts its values in increasing order, which is their smallest arrangement. With
i = -1, this reverses the whole array.
Traps
nums[j] < nums[i]in the swap scan. The scan stops on a value equal to the pivot. For[1, 5, 1], the result is[1, 1, 5]instead of[5, 1, 1].nums[i] > nums[i + 1]in the pivot scan. The scan stops on two equal values. For[1, 5, 5], thejscan runs past the front and Python raises an IndexError.- Returning early when there is no pivot.
[3, 2, 1]must become[1, 2, 3]. Reversing from index 0 does that. - Sorting the tail instead of reversing it. The answer is the same, but sorting costs
O(N log N)and the reversal costsO(N). - Using this card for a rank. If the statement gives
kand asks for thek-th arrangement, compute it directly.