Backtracking — Next Permutation

↗ LeetCode: Next Permutation · Medium · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftBloomberg

Rearrange nums to the next lexicographic permutation in-place. If none, sort ascending.

Example 1 — nums=[1,2,3] → [1,3,2]Example 2 — nums=[3,2,1] → [1,2,3] (last perm → wrap to first) Example 3 — nums=[1,1,5] → [1,5,1]

Constraints — 1 ≤ n ≤ 100. Brute enumerate all n! permutations + sort + look up next is O(n! · n log n) — 100! is beyond universe. Classic in-place algorithm is O(n). Brute generates all n! permutations then finds next — 10¹⁶⁵ ops at n=100 (dies). Linear scan from right to find pivot + swap + reverse suffix is O(n) = 100 ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Enumerate all n! permutations

Intuition. Generate all permutations in lex order (or sort them). Find the current one. Return the next.

Complexity — Time O(n! · n); Space O(n! · n). Beyond n=10. In an interview say "there's a beautiful O(n) in-place algorithm — pivot-swap-reverse."

---

Approach 2 — Classic algorithm (canonical)

Insight — 3-step pivot-swap-reverse:

1. Scan from right; find first i with nums[i] < nums[i+1] (pivot). If none, whole array is decreasing → reverse to ascending.
2. Scan from right; find first j with nums[j] > nums[i]. Swap i and j.
3. Reverse suffix from i+1 to end (was decreasing → becomes increasing = smallest larger permutation).

void nextPermutation(int[] nums) {
    int n = nums.length, i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    reverse(nums, i + 1, n - 1);
}
void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
void reverse(int[] a, int l, int r) { while (l < r) swap(a, l++, r--); }

Execution Trace

Classic algorithm (canonical)

Step 1 / 3Initialize scan.

Complexity — Time O(n); Space O(1). Say aloud in an interview: "same pattern in std::next_permutation in the C++ standard library, and itertools.permutations's iterative production."

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Enumerate all perms	O(n! · n)	O(n! · n)	Reference; fails past n=10
Classic 3-step	O(n)	O(1)	Canonical

When to use which

• Standard next-perm → this algorithm.
• Previous permutation → mirror the steps (scan for decreasing gap, etc).
• Kth permutation → factorial-number system.

✨AI Study CompanionBeta

Related problems

• Permutations
• Permutation Sequence

Was this page helpful?