Next Permutation — In-Place Algorithm

What does it solve?

Given an array, rearrange it into the next lexicographically greater permutation — the smallest arrangement that's still bigger than the current one.

If the array is already the last (fully descending) permutation, wrap around to the first permutation (fully ascending) — done in-place, without extra memory.

The core idea

// 1. scan right→left for a "pivot":
find rightmost i where a[i] < a[i+1]
// 2. find smallest value to its right that still beats it:
find rightmost j > i where a[j] > a[i]
swap(a[i], a[j])
reverse(a[i+1 .. end]) // make suffix smallest

Complexity

Time complexity

O(n)

Each of the three scans (pivot, successor, reverse) touches each index at most once.

Space complexity

O(1)

Done entirely in-place — just a swap and a suffix reversal, no extra array.

Examples & edge cases

Live animation

Comparing Pivot (i) Successor (j) Rejected Reverse pointer Done

Step — of —

Phase

—

Pivot (i)

—

Successor (j)

—

Step

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Phase	Indices	Array	Note

C++ implementation

next_permutation.cpp

#include <bits/stdc++.h>
using namespace std;

void nextPermutation(vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;

    // 1. Find the rightmost index where nums[i] < nums[i+1]
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;

    if (i >= 0) {
        // 2. Find the rightmost value greater than nums[i]
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }

    // 3. Reverse the suffix after i
    // (if i < 0, the whole array is descending -> this reverses it all,
    //  wrapping around to the first permutation)
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    vector<int> nums = {1, 2, 4, 3};
    nextPermutation(nums);

    for (int x : nums) cout << x << " ";
    cout << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars