31. Next Permutation

Rearrange the numbers into the next greater permutation in lexicographic order, in place. Scan from the right for the first ascent (the pivot), swap it with the smallest larger value to its right, then reverse the tail — all in O(n) time and O(1) space.

● MediumTwo PointersArrayTypeScript

PROBLEM What we're solving

Turn the array into the next permutation in dictionary order, in place. For nums=[1,2,3] the answer is [1,3,2]. For nums=[1,1,5] it is [1,5,1]. If the array is the very last permutation (fully descending) like [3,2,1], wrap around to the first: [1,2,3].

KEY IDEA Bump the rightmost ascent, then minimize the tail

Insight → a suffix that is fully non-increasing is already the largest it can be, so it cannot grow. The smallest possible increase comes from the rightmost index i where nums[i] < nums[i+1] (the pivot). Replace nums[i] with the smallest value to its right that is still larger, then make the now-descending tail as small as possible by reversing it.

RECIPE Find pivot · swap · reverse

1 · Find the pivot. Walk from the right while nums[i] >= nums[i+1]. The first place this breaks is the pivot i— because everything past it is already maximal and can't produce a bigger number.
2 · Swap with the next-larger. If a pivot exists, scan from the right for the first j with nums[j] > nums[i] and swap. Since the tail is descending, that first match is the smallest value that still exceeds the pivot — the minimal legal bump.
3 · Reverse the tail. After the swap the suffix after i is still descending; reversing it makes it ascending = the smallest ordering, giving the closest larger permutation.
0 · No pivot? The array is fully descending (the last permutation). Skip the swap and reverse the whole array to wrap to the first permutation.

Classic confusion → step 3 is a plain reverse, not a sort. Because the tail is guaranteed non-increasing both before and after the swap, reversing it is exactly equivalent to sorting it ascending — but it is O(n) instead of O(n log n). Sorting works but throws away the structure you already have.

COST Complexity & alternatives

Generate all perms, pick next

O(n! · n)

Enumerate every permutation — hopeless beyond tiny n.

Pivot · swap · reverse

O(n)

Two right-to-left scans + one reverse; O(1) space.

Why O(1) space

Everything happens with index math and in-place swaps — no auxiliary array. The work is three linear passes at most (find pivot, find swap target, reverse), so it is O(n) time and O(1) extra space.

Pattern transfer →the same "rightmost ascent, swap, reverse tail" engine drives Permutations when generated iteratively, and the mirror-image version (rightmost descent) yields Previous Permutation. The reverse-the-suffix trick also appears in Next Greater Element III(next permutation of a number's digits).

RUN IT Pivot, swap, reverse the tail

nums =

step 0 / 5

STARTFind the next lexicographic permutation in place. Scan from the right for the first i where nums[i] < nums[i+1].

1function nextPermutation(nums: number[]): void {
2▶  const n = nums.length;
3 
4  // 1. find pivot: first i from the right with nums[i] < nums[i + 1]
5  let i = n - 2;
6  while (i >= 0 && nums[i] >= nums[i + 1]) i--;
7 
8  // 2. if a pivot exists, swap it with the next-larger value to its right
9  if (i >= 0) {
10    let j = n - 1;
11    while (nums[j] <= nums[i]) j--;
12    [nums[i], nums[j]] = [nums[j], nums[i]];
13  }
14 
15  // 3. reverse the suffix after i so it becomes the smallest arrangement
16  let lo = i + 1, hi = n - 1;
17  while (lo < hi) {
18    [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
19    lo++; hi--;
20  }
21}

nums =102132

State

—

pivot i

—

swap j

—

cursor

scanning cursorpivot iswap target jsuffix being reversed

slowfast

TYPESCRIPT The solution, annotated

nextPermutation.ts
function nextPermutation(nums: number[]): void {
  const n = nums.length;

  // 1. find pivot: first i from the right with nums[i] < nums[i + 1]
  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;

  // 2. if a pivot exists, swap it with the next-larger value to its right
  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // 3. reverse the suffix after i so it becomes the smallest arrangement
  let lo = i + 1, hi = n - 1;
  while (lo < hi) {
    [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
    lo++; hi--;
  }
}

Reading it block by block

Lines 4–6 — find the pivot. Starting at n-2, move left while the array is non-increasing (nums[i] >= nums[i+1]). The first index where this fails is the pivot i; if we fall off the left end, i = -1 and the array was fully descending.

Lines 9–13 — swap with the next-larger. Only when a pivot exists. Scan from the right for the first j with nums[j] > nums[i]. Because the suffix descends, that first match is the smallest value exceeding the pivot — swapping yields the minimal increase to the prefix.

Lines 16–21 — reverse the tail. After the swap (or if there was no pivot, starting from index 0) the suffix after i is descending. A two-pointer reverse turns it ascending — the smallest tail — so the whole array is the closest larger permutation. When i = -1, this reverses the entire array.

Complexity → O(n) time — at most two right-to-left scans plus one reverse — and O(1) extra space (all in-place swaps).

INTERVIEWFollow-ups they'll ask

"What if there is no next permutation?" The pivot scan returns i = -1; we skip the swap and reverse the whole array, wrapping to the smallest (ascending) permutation.
"Handle duplicates?" The strict >= in the pivot scan and > in the swap scan already handle ties correctly — e.g. [1,1,5] → [1,5,1].
"Previous permutation instead?" Mirror every comparison: find the rightmost descent, swap with the largest smaller value, then reverse the tail.
"Next bigger number with the same digits?"That's Next Greater Element III — run this exact algorithm on the digit array, then re-join (watching for 32-bit overflow).

OPTIMAL Two Pointers

nextPermutation.ts
function nextPermutation(nums: number[]): void {
  const n = nums.length;

  // 1. find pivot: first i from the right with nums[i] < nums[i + 1]
  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;

  // 2. if a pivot exists, swap it with the next-larger value to its right
  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // 3. reverse the suffix after i so it becomes the smallest arrangement
  let lo = i + 1, hi = n - 1;
  while (lo < hi) {
    [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
    lo++; hi--;
  }
}

Complexity → O(n) time — at most two right-to-left scans plus one reverse — and O(1) extra space (all in-place swaps).

ALT 1 Brute force — enumerate permutations and pick the next

O(n! · n) time · O(n! · n) space

Generate every permutation, sort them lexicographically, find the current one, and return the one after it (wrapping to the first). Conceptually obvious but combinatorially explosive.

approach-2.ts
function nextPermutation(nums: number[]): void {
  const perms: number[][] = [];
  const permute = (arr: number[], cur: number[]): void => {
    if (arr.length === 0) { perms.push([...cur]); return; }
    for (let k = 0; k < arr.length; k++) {
      permute([...arr.slice(0, k), ...arr.slice(k + 1)], [...cur, arr[k]]);
    }
  };
  permute(nums, []);
  perms.sort((a, b) => a.findIndex((v, k) => v !== b[k]) === -1
    ? 0 : a[a.findIndex((v, k) => v !== b[k])] - b[a.findIndex((v, k) => v !== b[k])]);
  const key = (p: number[]): string => p.join(',');
  const idx = perms.findIndex((p) => key(p) === key(nums));
  const next = perms[(idx + 1) % perms.length];
  for (let k = 0; k < nums.length; k++) nums[k] = next[k];
}

Note → Correct but it materializes all n! permutations — unusable past a handful of elements, and it ignores the O(1)-space requirement. The pivot/swap/reverse method gets the same answer in a single in-place O(n) pass.

MNEMONIC The one-liner

"Rightmost ascent, swap up just enough, then flip the tail."

TRIGGERS When you see _ → reach for _

"next permutation in place"	pivot → swap → reverse tail
suffix already descending	cannot grow → look further left
swap target on a descending tail	first-from-right that beats pivot
fully descending array	no pivot → reverse everything

SKELETON The reusable shape

skeleton.ts
let i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;   // pivot
if (i >= 0) {
  let j = nums.length - 1;
  while (nums[j] <= nums[i]) j--;               // next-larger
  [nums[i], nums[j]] = [nums[j], nums[i]];       // swap
}
let lo = i + 1, hi = nums.length - 1;            // reverse tail
while (lo < hi) { [nums[lo], nums[hi]] = [nums[hi], nums[lo]]; lo++; hi--; }

FLASHCARDS Tap to flip

Where is the pivot?

The rightmost index i with nums[i] < nums[i+1] — the first ascent scanning from the right.

tap to flip

1 / 6

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Optimal time complexity?

QUESTION 02

The pivot is defined as:

QUESTION 03

After locating the pivot i, which element do you swap it with?

QUESTION 04

Why do you reverse the suffix after the pivot rather than sort it?

QUESTION 05

What happens when no pivot is found (the scan reaches index -1)?

QUESTION 06

For nums = [1,1,5], the next permutation is:

QUESTION 07

What is the extra space complexity?

QUESTION 08

#31 · Next PermutationRearrange numbers into the lexicographically next permutation in place: find the rightmost ascent, swap its pivot with the next-larger value to its right, then reverse the suffix. O(n) time, O(1) space.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Bump the rightmost ascent, then minimize the tail

RECIPE Find pivot · swap · reverse

COST Complexity & alternatives

Why O(1) space

RUN IT Pivot, swap, reverse the tail

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Two Pointers

ALT 1 Brute force — enumerate permutations and pick the next

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _