Next Permutation

TWO POINTERS · MEDIUM

Builds on Day 4: Two-Pointer Pattern

The optimal solution below is a two-pointer scan (find a pivot from the right, find its successor from the right, then reverse a suffix with two inward-moving pointers) — read that lesson first if the inward-pointer reversal technique is still a new idea.

The problem

nums is one particular ordering (a “permutation”) of a set of integers. Every possible ordering of those same values, if you sorted them all lexicographically like words in a dictionary, forms a sequence — and your job is to rearrange nums IN PLACE into whichever ordering comes immediately after the current one in that sequence. For example [1, 2, 3] becomes [1, 3, 2] — the very next arrangement after 1, 2, 3 once you start listing every permutation of {1, 2, 3} alphabetically. If nums already happens to be the LAST (most-descending) arrangement possible — like [3, 2, 1] — there’s nothing lexicographically greater, so it wraps around to the smallest one instead, [1, 2, 3]. Duplicate values are allowed and don’t get special treatment beyond ordinary numeric comparison — e.g. [1, 1, 5] → [1, 5, 1]. The rearrangement must happen in place, using only O(1) extra space.

Solution 1: Brute force — generate every permutation, sort, find the next one

The most literal reading of “next permutation in the sorted sequence of all permutations” is to actually build that sequence: generate every distinct permutation of nums (careful with duplicate values — two 5s swapped with each other don’t produce two “different” permutations, so duplicates must be de-duplicated), sort the whole list lexicographically, find where the current nums sits in that sorted list, and return whatever comes right after it — wrapping to the first entry if nums was last. This is a real, correct algorithm, not a strawman — but it is genuinely impractical: the number of permutations of n distinct values is n!, and sorting that list costs an extra log(n!) factor on top. 10! is already 3.6 million; 15! is over a trillion. This demo is deliberately capped at n = 3 (only 6 total permutations) just to keep it animatable at all — this is the definition of an approach that only works on toy inputs.

Interactive visualization

Tiny demo array [1, 2, 3] — only 6 total permutations, which is already close to the practical ceiling for animating this approach at all. Watch every permutation get visited in sorted order, the current nums get located, and the very next one become the answer.

a permutation being visited while scanning the sorted list the current nums arrangement, and the final answer

nums = [1, 2, 3] — only 6 total permutations

Press Play to scan through every permutation in sorted order.

Step 0 / 8

▶ Play↺ Reset

The code

function nextPermutationBrute(nums) {
  const n = nums.length;
  const sorted = nums.slice().sort((a, b) => a - b);
  const used = new Array(n).fill(false);
  const perms = [];

  (function backtrack(current) {
    if (current.length === n) {
      perms.push(current.slice());
      return;
    }
    for (let i = 0; i < n; i++) {
      if (used[i]) continue;
      if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      current.push(sorted[i]);
      backtrack(current);
      current.pop();
      used[i] = false;
    }
  })([]);

  const key = nums.join(',');
  const idx = perms.findIndex((p) => p.join(',') === key);
  const next = perms[(idx + 1) % perms.length];

  for (let i = 0; i < n; i++) nums[i] = next[i];
  return nums;
}

Line by line:

• sorted = nums.slice().sort(...) — start from the smallest possible arrangement so the backtracking search below visits every permutation in lexicographic order for free, instead of generating them in an arbitrary order and sorting afterward.
• The backtrack closure is a standard “build one permutation at a time” search: pick an unused position from sorted, recurse, then undo (backtrack) and try the next one.
• if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) continue; — the duplicate guard. Because sorted is sorted, equal values sit next to each other; skipping a repeated value whose identical predecessor hasn’t been used yet at this branch prevents generating the same permutation twice (e.g. two 1s swapped with each other don’t count as two different permutations).
• perms.findIndex((p) => p.join(',') === key) — locate exactly where the original nums sits in the sorted list of every distinct permutation.
• (idx + 1) % perms.length — the modulo is what implements “wrap to the first permutation if nums was the last one”: when idx is the final index, adding 1 and wrapping via % lands back on index 0.

Complexity

Time	Space	Approach
O(n! log n!)	O(n!)	Generate all permutations, sort, find next

Solution 2: Optimal — find pivot, swap with successor, reverse the suffix

Generating every permutation to find just the one right after nums is wasteful — there’s a purely local way to construct that exact next arrangement without ever looking at any other permutation. Scan nums from the right and find the rightmost index i where nums[i] < nums[i + 1] — call this the pivot. Everything to the right of i is, by definition, in non-increasing order (it’s already the “largest” arrangement of those values), so the current permutation is the largest one that shares its prefix up through index i. To get the very next permutation, increase nums[i] by the smallest possible amount: scan from the right again to find the rightmost index j > i where nums[j] > nums[i] — the smallest value in the suffix that’s still bigger than nums[i] — and swap them. The suffix is still non-increasing after that swap, which is the opposite of what we want (we want the smallest arrangement of it), so reverse it. If no pivot exists at all — nums is non-increasing top to bottom, e.g. [3, 2, 1] — the whole array is already the highest permutation, so just reverse it entirely to wrap to the lowest.

Interactive visualization

Demo array [1, 3, 5, 4, 2] — chosen so the pivot lands in the middle of the array (not at either end), so every phase of the algorithm (pivot scan, successor scan, swap, suffix reverse) is visible.

current scan index (i during the pivot search, or i held fixed during the successor search) value being compared against during the pivot or successor search the moment the pivot and its successor are swapped (also used for the paired reversal swaps) the suffix that’s about to be, or currently being, reversed the finished next permutation

nums = [1, 3, 5, 4, 2] — chosen so the pivot lands in the middle (every phase is visible)

Press Play to watch the optimal algorithm scan from the right.

Step 0 / 11

▶ Play↺ Reset

The code

function nextPermutationOptimal(nums) {
  const n = nums.length;

  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }

  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) {
      j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  let lo = i + 1;
  let hi = n - 1;
  while (lo < hi) {
    [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
    lo++;
    hi--;
  }

  return nums;
}

Line by line:

• i = n - 2 starting point, then while (i >= 0 && nums[i] >= nums[i + 1]) i--; — scan leftward from the second-to-last index as long as the array is non-increasing there, looking for the first break in that pattern. If the loop runs all the way to i = -1 without breaking, the entire array is non-increasing — no pivot exists.
• if (i >= 0) — only run the swap-and-partial-reverse path when a pivot was actually found. When i is -1, this block is skipped entirely and falls straight through to the reversal below, which — with lo = i + 1 = 0 — reverses the WHOLE array, which is exactly the “wrap to lowest” behavior needed.
• while (nums[j] <= nums[i]) j--; — scan from the last index leftward for the rightmost value still bigger than nums[i]. This is guaranteed to find something, because the suffix is non-increasing and nums[i] < nums[i + 1] by definition of the pivot — nums[i + 1] itself always qualifies as a fallback.
• [nums[i], nums[j]] = [nums[j], nums[i]] — destructuring swap. Both old values are read before either assignment happens, so it’s safe even though nothing else in this solution depends on assignment order the way some in-place array problems do.
• The final while (lo < hi) reverses everything from i + 1 (or from 0, in the no-pivot case) through the end — two inward-marching pointers swapping pairs, the same pattern taught in Day 4.
• Why reversing the suffix produces the smallest possible arrangement of it: the suffix was non-increasing (largest-to-smallest) before the swap, and swapping in a slightly bigger value at position i doesn’t change that the REST of the suffix (everything after i) is still exactly the same multiset of values in non-increasing order. Reversing a non-increasing sequence produces the non-decreasing (smallest-to-largest) arrangement of those same values — the smallest permutation of that suffix — which is exactly what “the very next permutation overall” requires.

Complexity

Time	Space	Approach
O(n)	O(1)	Find pivot, swap with successor, reverse suffix

Complexity comparison

Solution	Time	Space
Brute force (generate all, sort, find next)	O(n! log n!)	O(n!)
Optimal (pivot, swap, reverse suffix)	O(n)	O(1)

This is one of the more extreme brute-force-vs-optimal gaps on this site — a genuine factorial-to-linear improvement, not a constant-factor tweak. At n = 10 the brute force is already juggling 3.6 million permutations; at n = 20 it’s computing with numbers bigger than the count of atoms in a human body, while the optimal solution does the same job in about 20 array accesses and at most one swap-and-reverse pass. There’s no honest sense in which the brute force “still works fine” at realistic input sizes — it’s included here purely because it’s the literal reading of the problem, and seeing exactly how it blows up is the whole point of building it at all.

Interview corner

Why does reversing the suffix after the pivot always produce the smallest possible arrangement of those values?

• By construction, the suffix (everything after the pivot index i) is in strictly non-increasing order BEFORE the swap — that’s the entire definition of “pivot”: the rightmost place the non-increasing pattern breaks.
• Swapping in the successor at position i changes what value sits at i, but every value that was already in the suffix (aside from the one that got swapped out) is still there, still in non-increasing order relative to each other.
• A non-increasing sequence, reversed, becomes non-decreasing — and the non-decreasing arrangement of any fixed multiset of values is, by definition, the lexicographically smallest ordering of them. That’s exactly what’s needed to make the whole result “the next permutation” rather than some much larger jump forward.

Why must the successor search look for the rightmost value greater than nums[i], not just the first one found scanning from the left?

• The suffix can contain several values bigger than nums[i] — picking any old one and swapping it in would still produce A valid, larger permutation, but not necessarily the SMALLEST one larger than the original, which is what “next” specifically means.
• Because the suffix is non-increasing, scanning it from the right means values are encountered in increasing order — so the rightmost value that’s still bigger than nums[i] is guaranteed to be the smallest such value in the whole suffix.
• Swapping in the smallest possible legal replacement at position i is what keeps the increase as small as possible, which is exactly what makes the final result the immediate next permutation rather than some arbitrary larger one.

What happens when the pivot search finds no pivot at all — i ends up at -1 — and why does the same reversal code handle that case for free?

• No pivot means the entire array is non-increasing from left to right — that’s the single highest permutation possible for this multiset of values (e.g. [3, 2, 1] for {1, 2, 3}).
• The correct answer for the highest permutation is to wrap around to the lowest one, which is simply all the values sorted ascending.
• Because the suffix-reversal step always starts at i + 1, and i is -1 in this case, it starts at index 0 — reversing the ENTIRE array. A non-increasing array, reversed in full, becomes fully non-decreasing — exactly the lowest permutation. No special-case branch is needed; the same code path naturally does the right thing.

Trick question — after this runs, is result a fresh array or the same one as original?

const original = [1, 2, 3];
const result = original.reverse();
console.log(result === original);

• Answer: true — result and original are the SAME array reference. Array.prototype.reverse() mutates the array in place AND returns that exact same reference, it does not create a copy.
• This is directly relevant to the suffix-reversal step above: the two-pointer swap loop in nextPermutationOptimal mutates nums directly for the same reason — the problem requires an in-place rearrangement, and JS’s own built-in .reverse() models that exact “mutate and hand back the same reference” contract, which is why it’s safe (and idiomatic) to write return nums; at the end instead of building and returning a new array.
• The trap in real code: const copy = someArray; copy.reverse(); does NOT protect someArray from mutation — copy is just another name for the same array, not a clone. A genuine copy needs someArray.slice() or [...someArray] BEFORE reversing.

⚠ Trap: code that does const sortedCopy = arr; sortedCopy.reverse(); expecting arr to stay untouched will silently corrupt the caller’s original array — no error, no warning, just quietly wrong data anywhere else arr is used afterward.

Quiz

1. Why is the brute-force solution capped at tiny inputs (n around 6) in the demo above?

Generating and sorting every permutation of n values costs O(n! log n!) — it grows explosively even for modest nIt’s actually fine at any size — the cap is just to keep the animation on screenIt only breaks down when there are duplicate values in the array

2. What exactly does the “pivot” index represent in the optimal solution?

The rightmost index where nums[i] < nums[i+1] — the first break, from the right, in an otherwise non-increasing suffixAlways the exact middle index of the array, regardless of the valuesThe index holding the largest value anywhere in the array

3. Why does the successor search take the rightmost index j where nums[j] > nums[i], instead of any qualifying index?

Scanning the non-increasing suffix right-to-left visits values in increasing order, so the rightmost qualifying index holds the smallest value that still beats nums[i]It doesn’t actually matter which qualifying index is chosen — any of them produce the correct next permutationIt’s purely a performance choice — leftmost would also be correct, just slower

4. If the pivot search finds no pivot at all (i ends at -1), what does the algorithm do, and why is that correct?

It falls through to reversing the entire array — since nums was already the highest permutation, this correctly wraps to the lowest oneIt throws an error, since “no pivot” is treated as invalid inputIt leaves nums completely unchanged, since there’s nothing left to do

5. What does [1,2,3].reverse() return relative to the original array it was called on?

The exact same array reference, mutated in place — not a new copyA brand-new array with the reversed order, leaving the original untouchedundefined — reverse() only mutates, it doesn’t return anything