#31 Next Permutation
frequently reported atMetaAdobeBloombergMicrosoftWalmartInfosys
the problem
In plain words
Rearrange the numbers into the next bigger arrangement in dictionary (lexicographic) order — the one that would come right after the current one if you listed every arrangement in sorted order. If the current arrangement is already the biggest, wrap around to the smallest one (ascending order). Change the array in place, using O(1) extra memory.
in nums = [1,2,3]
out [1,3,2]
in nums = [3,2,1]
out [1,2,3]
[3,2,1] is the biggest arrangement, so wrap to the smallest.
in nums = [1,1,5]
out [1,5,1]
- 1 ≤ n ≤ 100
- 0 ≤ nums[i] ≤ 100
- In place, O(1) extra memory
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternNext permutation (pivot, swap, reverse)Two pointers (opposite ends)
where this runsC++'s std::next_permutation is this exact operation: it rearranges a range into the next permutation in lexicographic order, in place.
To grow the arrangement as little as possible, change it as far to the right as you can. The longest falling suffix is already at its biggest, so the number just before it (the pivot) must grow: swap in the smallest bigger value from the suffix, then reverse the suffix into its smallest order.
solutions
From brute force to optimal
Build all n! arrangements and keep the smallest one that is bigger than the input — or the smallest overall if none is bigger.
- Backtrack over unused positions to build each arrangement.
- Compare each one with nums; keep the smallest that is bigger.
- If none is bigger, use the smallest arrangement. Copy the answer into nums.
n! arrangements, each built and compared in O(n) — already 36,28,800 arrangements for n = 10.
Recursion depth n plus a few arrays of length n.
class Solution { private int[] best; // smallest arrangement found that is bigger than the input private int[] smallest; // smallest arrangement overall (the wrap-around answer) public void nextPermutation(int[] nums) { best = null; smallest = null; build(nums, new int[nums.length], new boolean[nums.length], 0); int[] answer = best != null ? best : smallest; // nothing bigger → wrap to the smallest System.arraycopy(answer, 0, nums, 0, nums.length); } private void build(int[] nums, int[] current, boolean[] used, int depth) { if (depth == nums.length) { // one complete arrangement: n! of them if (smallest == null || compare(current, smallest) < 0) smallest = current.clone(); if (compare(current, nums) > 0 && (best == null || compare(current, best) < 0)) best = current.clone(); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; used[i] = true; current[depth] = nums[i]; build(nums, current, used, depth + 1); used[i] = false; } } private int compare(int[] a, int[] b) { for (int i = 0; i < a.length; i++) if (a[i] != b[i]) return Integer.compare(a[i], b[i]); return 0; }}Find the first dip from the right, swap it with the rightmost bigger value, then reverse the falling suffix.
- i = n − 2; move left while nums[i] ≥ nums[i + 1] — everything after i is falling.
- If i ≥ 0: j = n − 1; move left while nums[j] ≤ nums[i]; swap nums[i] and nums[j].
- Reverse nums[i + 1 .. n − 1]. (No pivot means i = −1, so this reverses everything: the wrap-around.)
At most three passes over the suffix: find the pivot, find j, reverse.
A few indices; everything happens in place.
class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--; // walk left past the falling suffix if (i >= 0) { // a pivot exists: nums[i] < nums[i + 1] int j = nums.length - 1; while (nums[j] <= nums[i]) j--; // rightmost value just bigger than the pivot swap(nums, i, j); } reverse(nums, i + 1, nums.length - 1); // falling suffix → rising: its smallest order } private void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } private void reverse(int[] a, int left, int right) { while (left < right) swap(a, left++, right--); }}Dry run
in the room
How to say it in the interview
talk track
- Write the arrangements of [1,2,3] in order: 123, 132, 213, 231, 312, 321. Point at what changes from 132 to 213.
- Say the three steps before coding — pivot, successor, reverse — and why the suffix after the pivot is always falling.
- Mention the wrap-around: a fully falling array has no pivot, and reversing all of it gives the smallest arrangement.
traps
- Using
>instead of>=while looking for the pivot — duplicates like [1,5,1] break. - Swapping with the first bigger value from the left of the suffix instead of the rightmost one.
- Sorting the suffix instead of reversing it: correct, but O(n log n) — and it shows you missed that the suffix is already falling.
what they ask next
Follow-ups
Previous permutation?
Mirror every comparison: find the first i from the right with nums[i] > nums[i + 1], swap it with the rightmost value smaller than it, then reverse the suffix.
Next Greater Element III (LC 556): next bigger number with the same digits?
Run next permutation on the digits. Return −1 if there's no pivot or the result doesn't fit in an int.
The k-th permutation (LC 60)?
Don't call next k times. Use factorials: (k − 1) / (n − 1)! picks the first digit, and so on — O(n²).
before you submit
Edge cases to test
- n = 1 → nothing changes.
- Already the biggest ([3,2,1]) → wrap to [1,2,3].
- Duplicates ([1,5,1] → [5,1,1]): use ≥ and ≤ in both scans.
- All equal ([2,2,2]) → stays the same.
practise next
Similar problems
- #189Rotate ArrayMediumin Arrays & Strings
- #46PermutationsMediumin Backtracking