Build Next Permutation from First Principles Without STL

1. Why the Next Arrangement Exists

Before we build the algorithm, we need one simple idea to sit in your mind:

A permutation is not random chaos. It is an ordered arrangement, and ordered things usually have a “next” one — unless they are already at the end.

Think of it like the lane structure on Karachi’s Shahrah-e-Faisal at different moments in the day. Cars are not moving randomly; they are arranged in a pattern. If you slightly change that pattern, you get a new arrangement that is just a little further ahead. The road can look completely different after a small shift, but it is still the same road. That is the heart of next permutation: find the smallest change that moves us forward.

By the end of this course, you will be able to explain:

• why some arrangements have a next one and some do not,
• what it means for one arrangement to be the “next” one,
• and why the algorithm is built around making the smallest possible increase.

That last phrase is the anchor for the whole topic:

Next permutation means the next arrangement in lexicographic order, with the smallest possible jump forward.

If that sounds abstract right now, good — it should. We are going to turn it into something you can picture, reason about, and eventually reconstruct from scratch.

The key tension is this: if you change too much, you skip over the true next arrangement. If you change too little in the wrong place, you stay stuck. So the algorithm is really a search for balance — move forward, but only as much as necessary.

Once that clicks, the rest of the method stops feeling like a trick and starts feeling inevitable.

2. The Core Idea Behind Change

Remember earlier when we said the goal is the smallest possible jump forward? That sentence contains the whole algorithm in disguise.

To understand next permutation, you need to see the problem as a question of change. Not big change. Not any change. The least disruptive change that still moves the arrangement ahead.

That idea rests on a few truths.

1) Order is local, but comparison is global

A permutation is made of individual positions, but whether one permutation is “next” depends on the entire arrangement.

That sounds odd at first, so think of it like arranging books on a shelf. If you swap two books at the front, that may completely change which shelf arrangement comes next in the sorted list of all possible shelves. A tiny local move can have a huge effect on the global order.

This is the same idea showing up again: small changes can create a much larger shift in rank.

In next permutation, we do not just ask, “What can I change?” We ask, “What is the smallest change that makes this arrangement larger than before?” That means we have to think about position by position, but judge the result against the whole ordering.

Core truth: the next permutation is not about rearranging everything. It is about finding the earliest place where a small change can create a larger sequence.

2) The right side matters less than the left side

Here is one of the most important mental models in this topic:

The rightmost part of the sequence is where local flexibility lives.

Why? Because numbers on the right are compared later. If you change something near the end, you affect the order less than if you change something near the beginning.

Imagine a word written from left to right. Changing the last letter usually changes the word less than changing the first letter. That is why the algorithm pays close attention to the right end first.

Think of it like a row of dominoes. The dominoes on the far right are the easiest place to make a small adjustment without disturbing the rest of the chain. The left side is more influential. If you want the smallest possible jump forward, you should disturb the left side only when absolutely necessary.

So the algorithm begins by searching from the right, not because the right is more important, but because it is the best place to make a minimal change.

Core truth: the farther right you make your change, the smaller the increase tends to be.

3) A decreasing suffix means “we are at the end of a local block”

Now let’s get to the key pattern.

When you scan from right to left and notice the numbers are going downward, that part of the array is in the greatest order possible for those exact elements.

Example idea, without focusing on code:

• ... 7 5 4 2
• ... 9 6 3

These right-side pieces are already arranged as large as they can be for those digits.

Why does that matter? Because if the tail is already in descending order, there is no way to make a smaller forward move using only that tail. It is already the last arrangement of that block.

Think of a stack of plates sorted from largest at bottom to smallest on top. If you look only at the top part and it is already in the “finished” order, you cannot create a slightly larger arrangement just by shuffling the top among itself. You need to reach one position to the left and use that as the place where progress happens.

This is the first real shift in understanding:

A descending suffix is not a problem. It is a signal.

It tells you: “The action must happen just before me.”

That is why the algorithm hunts for the place where this descending run begins. Everything to the right of that place is already in its highest internal form.

4) The pivot is the first place where increase becomes possible

Once you know the suffix is descending, the next question is: where can the sequence still be increased without skipping too far?

The answer is the pivot — the first element from the right that is smaller than something to its right.

That is the point where the arrangement stops being “as large as possible” and becomes “still adjustable.”

A good analogy is a staircase. If you walk from right to left and the steps keep going down, then the first step that suddenly allows you to move upward is the one you care about. That step is your pivot.

Why is the pivot so important? Because it is the leftmost point of minimal disturbance. If you change anything farther left than the pivot, you change too much. If you try to change only the suffix, you cannot get a larger arrangement because the suffix is already maximized.

So the pivot is the bridge between two worlds:

• to its right: the sequence is already as large as it can be,
• at the pivot: a larger arrangement becomes possible.

Core truth: the pivot is the first place where the current arrangement can be made bigger without rewriting the whole sequence.

5) To get the next one, you must increase just enough, then minimize the rest

This is the heart of the algorithm’s logic.

Once you find the pivot, you need to make it slightly larger. But not just any larger value — the smallest value that is still bigger than the pivot.

Why? Because the moment you increase the pivot, you have already moved to a new region of the ordering. If you increase it too much, you skip over valid permutations that should come before your answer.

A helpful analogy is setting a staircase on a building floor. If you need to go up one floor, you do not jump to the tenth floor just because it is higher. You choose the nearest higher floor.

This is the same idea in next permutation:

• the pivot must rise,
• but it must rise by the smallest amount possible.

Then, after that increase, the right side must be put into its smallest possible order. Why? Because once the left side is fixed, the only way to keep the whole permutation as small as possible is to make the suffix minimal.

Remember earlier when we said the right side is where flexibility lives? Here it becomes clear why. The suffix is the part we can rearrange to preserve minimality after the key increase.

So the algorithm has a very precise rhythm:

1. find the point where increase is still possible,
2. raise it by the smallest meaningful amount,
3. make everything to the right as small as possible.

That is not a trick. It is the logic of lexicographic order.

6) Why reversing the suffix works

At this point, one question naturally appears: if the suffix was descending, why does turning it around help?

Because descending order is the largest arrangement of that suffix. But after you increase the pivot, you want the suffix to become the smallest arrangement possible.

And the smallest arrangement of a set of digits is just them in ascending order.

So if the suffix is currently descending, reversing it makes it ascending.

That is a beautiful little symmetry:

• before the pivot change, the suffix is at its maximum form,
• after the pivot change, the suffix must become its minimum form.

Imagine a set of colored beads laid out from big to small. If you have already chosen the bead at the pivot to move upward, the beads on the right should be arranged in the gentlest, earliest order so the whole sequence stays as low as possible.

This is the same idea showing up again: make the smallest allowed change, then minimize everything that comes after it.

The mental model to keep

If you only remember one thing from this section, make it this:

Next permutation is about finding the rightmost place where you can make a small increase, then cleaning up the rest so the total change is as small as possible.

That sentence is the engine behind the whole algorithm.

Once this clicks, the algorithm stops looking like a memorized recipe and starts looking like a natural response to the structure of order itself.

In the next section, we will turn these truths into the exact mechanism that makes the algorithm work on any array, including the cases where no next permutation exists.

3. Building the Algorithm in C++

Now that the logic is clear, the code becomes much less mysterious.

Remember earlier when we said the whole problem is about finding the rightmost place where a small increase is still possible? That idea is not just a conceptual trick — it is exactly how the implementation is organized.

The algorithm has three jobs:

1. Find the pivot — the first element from the right that can still be increased.
2. Find the smallest element on the right that is bigger than the pivot.
3. Reverse the suffix so the tail becomes the smallest possible arrangement.

If Section 2 was the “why,” this section is the “how it becomes code.”

The shape of the solution

A permutation in memory is just an array. The job is to transform that array in place so it becomes the next lexicographic arrangement.

That matters because the algorithm is not really creating something new. It is rearranging what already exists.

Think of it like reorganizing a shelf of books. You do not buy new books to make the next arrangement; you move the existing ones into a new order. Same with the array.

In C++, that means we usually work with:

vector<int>& nums

or a raw array if the problem asks for it. The logic stays the same.

The pivot search

The first thing we want is the pivot.

Why from the right? Because, as we said before, the right side is where the smallest change can happen. We scan from right to left until the descending pattern breaks.

What are we looking for exactly?

We want the first index i such that:

nums[i] < nums[i + 1]

That means position i is the place where the sequence can still rise.

If you imagine the array as a road, the descending suffix is the stretch of road going downhill. The pivot is the first point where you can still climb upward instead of being forced to keep going down.

Why this works

Everything to the right of the pivot is already in descending order, which means it is the largest arrangement of that suffix. So if we want the next permutation, the change must happen at or before the pivot.

This is the same logic from earlier, now made concrete.

The successor search

Once the pivot is found, we need the smallest value on the right that is still larger than the pivot.

Suppose the pivot value is 3. The suffix might contain 9, 7, 5, 4. We do not want 9 if 4 works. We want the smallest number greater than 3, because that gives us the smallest increase overall.

So from the right side, we scan again until we find the first value greater than nums[i].

Why from the right again?

Because the suffix is descending. That means the first value we encounter from the end that is greater than the pivot is automatically the smallest valid larger value.

That is a very important connection:

Because the suffix is descending, the rightmost valid successor is the best successor.

This is a beautiful example of how the earlier structure saves us work. We do not need to search the whole suffix carefully. The order of the suffix itself tells us where the answer is.

Swap the pivot and successor

Once we find that successor, we swap it with the pivot.

This is the moment the arrangement actually moves forward.

But notice something subtle: after the swap, the suffix is no longer in the order we want. That is okay. We expected that. The swap is only responsible for making the sequence larger. It does not yet make the whole result minimal.

Think of it like unlocking a door. Swapping the pivot and successor is the key that opens the next state, but the room is still messy until we clean the suffix.

Reverse the suffix

After the swap, the part to the right of the pivot must become as small as possible.

Before the swap, that suffix was descending. After the swap, it is still made of the same elements, just in a slightly disturbed order. The smallest arrangement of those elements is ascending order.

And here is the clever part:

If a segment is descending, reversing it makes it ascending.

So instead of sorting the suffix, we simply reverse it.

That is not a shortcut by accident. It is a consequence of the structure we already proved.

The suffix starts as descending because it was the largest possible tail.

After the pivot increase, the suffix must become ascending because it should now be the smallest possible tail.

The reverse step is the final cleanup that turns a larger arrangement into the next arrangement rather than just a bigger one.

A full example in motion

Let’s use a simple sequence:

1 2 3 6 5 4

We want the next permutation.

1) Find the pivot

Scan from the right:

• 5 > 4 — still descending
• 6 > 5 — still descending
• 3 < 6 — stop

So 3 is the pivot.

2) Find the successor

In the suffix 6 5 4, find the smallest number greater than 3.

Because the suffix is descending, the rightmost number greater than 3 is 4.

3) Swap pivot and successor

Now we get:

1 2 4 6 5 3

4) Reverse the suffix

Reverse everything after 4:

1 2 4 3 5 6

That is the next permutation.

Notice how the change is tiny but meaningful:

• the left part before the pivot stayed the same,
• the pivot increased by the smallest possible amount,
• the remaining numbers became the smallest possible tail.

This is exactly the “smallest jump forward” principle from Section 1.

What if no pivot exists?

Sometimes the whole array is in descending order.

Example:

5 4 3 2 1

If you scan from right to left, you never find nums[i] < nums[i + 1].

What does that mean?

It means this is the largest possible permutation of those elements. There is no next one.

So what should the algorithm return?

The answer is the smallest permutation, which is the ascending order:

1 2 3 4 5

This fits the same logic we have been building all along. If you are already at the end of the ordering, you wrap around to the beginning.

That is why many implementations say: if no pivot is found, just reverse the entire array.

Why the algorithm is in-place

A strong feature of next permutation is that it can be done in place.

That means we only need a few variables, not extra storage proportional to the array size.

This works because we are not generating a new permutation from scratch. We are using the current order, recognizing its structure, and modifying it carefully.

The algorithm is efficient because the structure tells us where the action is:

• the pivot tells us where increase is possible,
• the suffix tells us where minimal rearrangement lives,
• the reverse operation turns that suffix into the right shape.

This is the same idea showing up again: the order itself contains the instructions.

A compact C++ implementation

Here is the standard version in C++:

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

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

    // 1. Find pivot
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    // 2. If pivot exists, find successor and swap
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums[i], nums[j]);
    }

    // 3. Reverse suffix
    reverse(nums.begin() + i + 1, nums.end());
}

Let’s connect the code to the idea:

If you understand the story, the code is almost just a translation.

A few subtle points worth noticing

1) The pivot index starts at n - 2

We compare nums[i] with nums[i + 1], so the rightmost useful starting point is the second last element.

2) The successor search starts from the far right

That is because the suffix is descending. The first number from the right that is greater than the pivot is the smallest valid choice.

3) reverse is enough

We do not need sort. The suffix is already in descending order before the swap, and after the swap, reversing gives the minimum order for that same set of numbers.

That is a great example of understanding saving effort.

The complete mental model

If you can explain this in your own words, you understand the algorithm:

Find the last place where the sequence can still go up. Increase it by the smallest possible amount. Then make everything after it as small as possible.

Or even shorter:

Pivot, successor, reverse.

But do not treat those three words as a memorization trick. They are a compressed version of the logic we have already built.

Remember earlier when we said the right side is where flexibility lives? Now you can see that flexibility is exactly what lets the algorithm work in linear time and constant extra space.

That is the real payoff: not just knowing the procedure, but seeing why the procedure is almost forced by the definition of “next.”

A local example of the same idea

Imagine a sequence of product IDs in a Karachi warehouse system, where the IDs must be ordered and updated to the next valid arrangement for batching. You would not want to reshuffle the entire list when only a tiny forward move is needed. You would look for the rightmost place where a minimal increase can happen, make that increase, and keep the rest as small as possible.

That is exactly what this algorithm is doing, only without the warehouse context. The system is the same.

What you should now be able to see

At this point, next permutation should no longer feel like a magic sequence of commands.

You should be able to see the hidden structure:

• the array has a right side that is already maximized,
• the pivot is the first place where movement is still possible,
• the successor gives the smallest safe increase,
• the reversed suffix restores minimality.

That is the whole machine.

In the next section, we will test this understanding against edge cases, common mistakes, and the final intuition that makes the algorithm feel fully yours.

4. Why This Skill Sticks

You made it to the point where the algorithm is no longer a sequence of mysterious actions. That is the real win here.

You now understand why the pivot exists, why the suffix matters, and why reversing works instead of sorting. Those are not three separate facts anymore — they are one system. The pivot tells you where the first meaningful increase can happen. The successor tells you how to increase without jumping too far. The reverse step restores the smallest possible tail so the result becomes the true next permutation, not just a bigger one.

That is the shift: you are no longer thinking like someone repeating a pattern. You are thinking like someone who can look at an array and read its structure.

You now think like a person who can see order, not just numbers.

That matters because once you see the logic here, you start recognizing the same shape in other problems:

• find the last place where change is still possible,
• make the smallest useful change,
• then clean up the rest so the outcome stays minimal.

That pattern is why this topic sticks. It is not about memorizing pivot → successor → reverse. It is about recognizing that a sequence contains its own next move if you know where to look.

And that means you can now do something more powerful than solve this one problem: you can explain why a greedy-looking local change produces the correct global result.

What you should feel now

• Clearer about lexicographic order
• More confident reading descending suffixes
• Able to predict when no next permutation exists
• Ready to teach the logic without leaning on STL shortcuts

The lasting idea

If the array is a story, the suffix is the part that has already reached its highest possible ending. The pivot is the one sentence that can still change. And the reverse step makes sure the new ending is as gentle as possible.

That is why this algorithm stays with you: it is built from a simple truth about order itself.

So the next time you see a permutation problem, you will not start from confusion. You will start from structure. And once you can see structure, the rest becomes much easier to trust.

That is the skill. And now it is yours.