STEP 3 · ARRAYS · SUFFIX PIVOT + REVERSE · MEDIUM

Next Permutation

WHAT IT SAYS

Rearrange the array in place into the next lexicographically greater permutation of its numbers, or into the smallest one if no greater permutation exists.

WHAT IT'S REALLY ASKING

"Read the array from the right. A stretch that is already falling has nowhere left to go — it is the biggest thing its own numbers can spell. So the real question is: how far right can you stay, find the last digit that still has room to grow, give it the smallest raise it can accept, and then make everything behind it as small as possible?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Generate every permutation and sort them

O(n! * n log n) time and O(n! * n) space

Enumerate all n! arrangements, sort the list lexicographically, find yours, and return the one after it. It answers the question by definition.

WHERE THE WORK IS WASTED — You construct n! arrangements to look at exactly one neighbour. Almost all of that work is spent ordering permutations that differ from the input in their leading elements — arrangements the answer will never come near, because the *next* permutation is by definition the smallest change that still increases, and the smallest change lives as far right as it can. Sorting the whole list is like alphabetising a dictionary to find the word after 'cat'.

KEY OBSERVATION — THE UNLOCKlink

A falling suffix is already maximal — it cannot grow.

Scan from the right and find the longest non-increasing run: 6, 5, 4 at the tail, say. Ask what permutations of just those three numbers exist. The answer is that 6,5,4 is the *largest* of them — sorting a multiset in descending order is the definition of its maximum arrangement. So there is no way to rearrange that suffix into something bigger. It has no next move. That single fact locates the pivot for you. If the tail can't grow, and lexicographic comparison is decided by the leftmost difference, then any increase must be paid for by a position to the LEFT of that falling run. But you also want the change to be as far right as possible (a change further left would jump you past permutations that only differ in the tail — you'd skip valid answers). So the position that changes is the first index i, coming from the right, where a[i] < a[i+1] — the last element that has anything bigger than itself to its right. That is forced: not a heuristic, the only candidate. If no such i exists, the whole array is one falling run, i.e. the maximum permutation. There is nothing after it — so you wrap around to the minimum, which is the whole thing reversed.

KEY OBSERVATION — THE UNLOCKlink

Smallest raise first, then the smallest possible tail.

The pivot must increase — but by the least amount possible, or you overshoot the immediate successor. The candidates for its new value are exactly the elements to its right that are bigger than it, and you want the smallest of them. Because that suffix is non-increasing, the smallest such element is the *rightmost* one that exceeds the pivot: walk from the end and stop at the first element greater than a[i]. Now swap them. The suffix stays non-increasing — you removed a value and dropped in a smaller-or-equal one in a slot where that order still holds — which means the tail is still sitting at its own maximum. But the prefix just went UP, so every arrangement of the tail now yields a permutation greater than the original. To be the *next* one, the tail must be the smallest arrangement of its numbers: sorted ascending. And here is the payoff: the tail is already descending, so 'sort ascending' is just 'reverse'. No sort, no comparison — the invariant you leaned on for the pivot hands you the final step for free.

Pivot, successor, reverse

O(n) time, O(1) space

Walk left from the end to find the first i with a[i] < a[i+1]; if there is none, reverse the whole array and stop. Otherwise walk left from the end again to find the first j with a[j] > a[i], and swap i and j. Then reverse everything after i — three linear passes, in place, no extra memory.

WHAT YOU TRADED — The O(1) space and the missing sort are both bought with a proof: every step here is standing on the invariant that the suffix is non-increasing, and if you break that invariant (say, by sorting the suffix before swapping) the shortcuts collapse. The transferable lesson: when a problem asks for the *next* thing in an order, look for the largest suffix that is already saturated — the change is always at its boundary.

WATCH THE IDEA RUN

phase scan

pivot not found yet

Start at the right edge and read backwards. You are hunting for the last place where the array stops falling.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Rightmost Room to Grow

YOU'LL SEE IT AGAIN WHEN

The statement asks for the next / previous item in a lexicographic or ranked order, not for a search over all items.
The structure has a suffix that is already extremal (fully sorted one way), which means the answer must change something just before it.
Minimality is required — 'next' means 'smallest increase' — so the change should happen as far right as possible and be as small as possible.

SAME BLUEPRINT, DIFFERENT PROBLEM

Permutation SequenceNext Greater Element IIIPrevious Permutation With One SwapPermutations (backtracking, for contrast)

The bar isn't "solved it once." It's "could rebuild it from the observation."