Next Permutation

The problem

Think of the odometer in an old car, but each digit can be any value and no digit repeats. You're showing arrangements of [1, 2, 3] in dictionary order: 123, 132, 213, 231, 312, 321. Someone hands you 123 and asks for the next one, 132. Hand them 321 and there is no next — you wrap back to 123.

The task: given one arrangement, produce the immediately next arrangement in lexicographic (dictionary) order, using the same elements. And do it in place, without listing all the permutations first.

A first attempt

The brute-force route: generate every permutation, sort them all, find yours in the list, and return the one after it. With n elements there are n! permutations — for just 12 elements that's nearly half a billion arrangements to build and sort. You'd burn O(n!) time and memory to answer a question about a single step. There has to be local structure we can exploit instead.

The insight

Read the arrangement from the right and notice what makes 321 the last one: it's fully descending. A descending tail is already maxed out — it can't get any bigger. So the only way to increase the number by the smallest possible amount is:

1. Find the rightmost spot where the order breaks — an element smaller than the one just after it. Call its index the pivot.
2. Swap the pivot with the smallest element to its right that still beats it. This nudges the number up by the least amount possible at that position.
3. The tail after the pivot is still descending; reverse it to make it ascending — the smallest possible ending.

If there's no pivot at all, the whole thing was descending (the last permutation), so just reverse it to wrap around to the first.

How it works

Take [1, 3, 5, 4, 2]. The next permutation is [1, 4, 2, 3, 5].

[1, 3, 5, 4, 2]
    ^pivot=3 (arr[1] < arr[2])
find rightmost > 3 in tail [5,4,2] -> 4, swap:
[1, 4, 5, 3, 2]
reverse tail after pivot [5,3,2] -> [2,3,5]:
[1, 4, 2, 3, 5]   ✓

The code

The tail reversal reuses the two-pointer sweep from Array Traversal Tricks.

def next_permutation(arr):
    n = len(arr)
    i = n - 2
    while i >= 0 and arr[i] >= arr[i + 1]:   # find the pivot
        i -= 1
    if i >= 0:                               # not the last permutation
        j = n - 1
        while arr[j] <= arr[i]:              # rightmost value bigger than pivot
            j -= 1
        arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1:] = reversed(arr[i + 1:])      # reverse the tail (whole array if i == -1)

function nextPermutation(arr: number[]): void {
  const n = arr.length;
  let i = n - 2;
  while (i >= 0 && arr[i] >= arr[i + 1]) i--;
  if (i >= 0) {
    let j = n - 1;
    while (arr[j] <= arr[i]) j--;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  let lo = i + 1, hi = n - 1;                // reverse the tail
  while (lo < hi) {
    [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
    lo++;
    hi--;
  }
}

void nextPermutation(int[] arr) {
    int n = arr.length, i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (arr[j] <= arr[i]) j--;
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
    int lo = i + 1, hi = n - 1;
    while (lo < hi) {
        int tmp = arr[lo]; arr[lo] = arr[hi]; arr[hi] = tmp;
        lo++; hi--;
    }
}

void next_permutation(int *arr, int n) {
    int i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (arr[j] <= arr[i]) j--;
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
    int lo = i + 1, hi = n - 1;
    while (lo < hi) {
        int tmp = arr[lo]; arr[lo] = arr[hi]; arr[hi] = tmp;
        lo++; hi--;
    }
}

#include <vector>
#include <algorithm>
using namespace std;

void nextPermutation(vector<int>& arr) {
    int n = (int)arr.size(), i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (arr[j] <= arr[i]) j--;
        swap(arr[i], arr[j]);
    }
    reverse(arr.begin() + (i + 1), arr.end());
}

Complexity

Three simple scans — find pivot, find successor, reverse tail — and never more than O(n) work total.

When to use it

Practice

Recap

• Next permutation finds the immediately-larger arrangement in dictionary order in O(n) time and O(1) space — no need to enumerate all n! of them.
• The recipe: find the rightmost pivot where order breaks, swap it with the smallest larger element to its right, then reverse the descending tail.
• A fully descending array has no pivot; reversing the whole thing wraps it back to the first permutation.