Next Permutation
Rearrange an array into the next lexicographically larger permutation in place: find the pivot from the right, swap it with its successor, reverse the suffix.
Problem Understanding
Next Permutation: rearrange nums in place into the next permutation in lexicographic order. If it is already the largest, rearrange it into the smallest (sorted ascending). Use O(1) extra memory.
Examples: [1,2,3] → [1,3,2]; [3,2,1] → [1,2,3]; [1,1,5] → [1,5,1].
The Intuition: Change As Little As Possible, As Far Right As Possible
Think of the array as a number you want to increase by the smallest step:
- The longest non-increasing suffix cannot grow. It is already its own largest arrangement.
- So the change happens at the pivot, the element just left of that suffix.
- Grow the pivot minimally: swap it with the smallest larger value in the suffix.
- Make the suffix as small as possible: it is still non-increasing, so reverse it.
The reverse is the same two pointers swap used in Reverse String and Rotate Array. To list every permutation rather than the next one, see Permutations.
Interactive Walkthrough
TINTED = THE SUFFIX AFTER THE PIVOT
FIND THE PIVOT
0
1
2
3
4
pivot
:
successor
:
nums[3] = 4 ≥ nums[4] = 2: still non-increasing from the right, keep going left
Next
nums[2] = 5 ≥ nums[3] = 4: still non-increasing from the right, keep going left
nums
The cells being compared or swapped are solid. Once found, the pivot is marked i, and the suffix after it, the part that gets rearranged, is tinted. Try Last one to see the wrap-around case.
Dry Run Table
Input: [2,6,5,4,3,1].
| Step | What happens | Array |
|---|---|---|
| Pivot | 6,5,4,3,1 is non-increasing; 2 < 6, so i = 0 | [2,6,5,4,3,1] |
| Successor | from the right, 1 ≤ 2, then 3 > 2, so j = 4 | [2,6,5,4,3,1] |
| Swap | swap i = 0 and j = 4 | [3,6,5,4,2,1] |
| Reverse | swap 1↔5, then 2↔4 | [3,1,2,4,5,6] |
Answer: [3,1,2,4,5,6].
The Solution Template
Three linear passes from the right, all in place.
Next Permutation Code
1var nextPermutation = function(nums) {2 let i = nums.length - 2;3 while (i >= 0 && nums[i] >= nums[i + 1]) i--;4 if (i >= 0) {5 let j = nums.length - 1;6 while (nums[j] <= nums[i]) j--;7 [nums[i], nums[j]] = [nums[j], nums[i]];8 }9 for (let l = i + 1, r = nums.length - 1; l < r; l++, r--) {10 [nums[l], nums[r]] = [nums[r], nums[l]];11 }12};
Edge Cases & Common Mistakes
- Last permutation: no pivot, so reverse the whole array.
- Strict comparisons: use
>=for the pivot scan and<=for the successor scan, or duplicates break it. - Sorting the suffix: works but costs O(n log n); the suffix is already non-increasing, so a reverse is enough.
- One element: nothing changes.
- Returning a new array: the problem wants the change in place.
Summary
Find the pivot (first nums[i] < nums[i + 1] from the right), swap it with the rightmost larger value, and reverse the suffix after it. If there is no pivot, reverse everything. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet