Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
A complete visual walkthrough of the three-step algorithm — find the dip, swap, and reverse.
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
arr = [1,2,3] is [1,3,2].arr = [2,3,1] is [3,1,2].arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3] Output: [1,3,2]
Example 2:
Input: nums = [3,2,1] Output: [1,2,3]
Example 3:
Input: nums = [1,1,5] Output: [1,5,1]
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100The brute force approach: generate all permutations in sorted order, find the current one, and return the next. For an array of length n, there are n! permutations — far too many.
Current permutation is [1,2,3], so the next one is [1,3,2]. But generating all 6 permutations just to find the next one is wasteful.
For n = 20, there are over 2.4 quintillion permutations. We need an O(n) approach that modifies the array in-place.
The key observation: To find the next permutation, we only need to make the smallest possible change to the array that makes it lexicographically larger. This change always happens at a specific pattern: the rightmost "dip" in the sequence.
The algorithm has exactly three steps, each with a clear purpose.
nums[i] < nums[i+1]. This is the point where the descending suffix begins. Everything to the right of i is already in the largest possible arrangement.Why does this work? The dip at index i means everything to its right is in descending order — the largest possible suffix. To get the next permutation, we need to increase the value at position i (swap) and then make the suffix as small as possible (reverse to ascending).
Let's trace through a detailed example to see each step clearly.
nums[7]=3 >= nums[8]=1 — not a dip, continue.nums[6]=5 >= nums[7]=3 — not a dip, continue.nums[5]=6 >= nums[6]=5 — not a dip, continue.nums[4]=7 >= nums[5]=6 — not a dip, continue.nums[3]=4 < nums[4]=7 — Found the dip at i=3!
nums[8]=1 <= 4 — skip.nums[7]=3 <= 4 — skip.nums[6]=5 > 4 — Found! Swap nums[3] and nums[6].
<= comparisons handle duplicates correctly.class Solution { public void nextPermutation(int[] nums) { // Step 1: Find the dip (rightmost i where nums[i] < nums[i+1]) int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--; // Step 2: If dip exists, swap with successor if (i >= 0) { int j = nums.length - 1; while (nums[j] <= nums[i]) j--; // find smallest > nums[i] swap(nums, i, j); } // Step 3: Reverse the suffix after index i reverse(nums, i + 1, nums.length - 1); } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } private void reverse(int[] a, int l, int r) { while (l < r) swap(a, l++, r--); } }
func nextPermutation(nums []int) { // Step 1: Find the dip (rightmost i where nums[i] < nums[i+1]) i := len(nums) - 2 for i >= 0 && nums[i] >= nums[i+1] { i-- } // Step 2: If dip exists, swap with successor if i >= 0 { j := len(nums) - 1 for nums[j] <= nums[i] { j-- // find smallest > nums[i] } nums[i], nums[j] = nums[j], nums[i] } // Step 3: Reverse the suffix after index i l, r := i+1, len(nums)-1 for l < r { nums[l], nums[r] = nums[r], nums[l] l++ r-- } }
def next_permutation(nums: list[int]) -> None: # Step 1: Find the dip (rightmost i where nums[i] < nums[i+1]) i = len(nums) - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 # Step 2: If dip exists, swap with successor if i >= 0: j = len(nums) - 1 while nums[j] <= nums[i]: j -= 1 # find smallest > nums[i] nums[i], nums[j] = nums[j], nums[i] # Step 3: Reverse the suffix after index i l, r = i + 1, len(nums) - 1 while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1
impl Solution { pub fn next_permutation(nums: &mut Vec<i32>) { // Step 1: Find the dip (rightmost i where nums[i] < nums[i+1]) let n = nums.len(); let mut i = n.wrapping_sub(2); while i < n && nums[i] >= nums[i + 1] { i = i.wrapping_sub(1); } // Step 2: If dip exists, swap with successor if i < n { let mut j = n - 1; while nums[j] <= nums[i] { j -= 1; // find smallest > nums[i] } nums.swap(i, j); } // Step 3: Reverse the suffix after index i let start = if i < n { i + 1 } else { 0 }; nums[start..].reverse(); } }
function nextPermutation(nums: number[]): void { // Step 1: Find the dip (rightmost i where nums[i] < nums[i+1]) let i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--; // Step 2: If dip exists, swap with successor if (i >= 0) { let j = nums.length - 1; while (nums[j] <= nums[i]) j--; // find smallest > nums[i] [nums[i], nums[j]] = [nums[j], nums[i]]; } // Step 3: Reverse the suffix after index i let l = i + 1, r = nums.length - 1; while (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; } }
Enter an array and step through the dip-finding, swap, and reverse operations visually.
Each of the three steps scans at most n elements: finding the dip is O(n), finding the swap target is O(n), and reversing the suffix is O(n). Total: O(n). The algorithm modifies the array in-place with only a constant number of extra variables, giving O(1) space.
Generate all n! permutations, sort them lexicographically, locate the current permutation, and return the next one. The recursive generation branches n ways at the first position, n-1 at the second, and so on -- producing n! results that must all be stored and sorted.
Three sequential linear scans: find the rightmost dip by scanning right-to-left (at most n comparisons), find the swap target by scanning the suffix (at most n), and reverse the suffix with two converging pointers (at most n/2 swaps). Each step is O(n), totaling O(n). Everything is done in-place with only index variables.
The suffix after the rightmost ascent is in descending order -- that is the key observation. This three-step in-place algorithm (find dip, swap with successor, reverse suffix) achieves both optimal time and space. We must at least read the array, which is already O(n), so we cannot do better.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.