The next
permutation

Rearrange into the next arrangement in dictionary order

List every permutation and sort them lexicographically; "next permutation" is the one right after the current array. [1,2,3] → [1,3,2], [2,3,1] → [3,1,2]. If the array is already the largest ([3,2,1]), wrap around to the smallest ([1,2,3]). Generating all N! arrangements is impossible even for N=100, and the constraint is in-place, O(1) space — so the next arrangement has to be derived directly.

Smallest increase = change as far right as possible

Lexicographic order is dictionary order: compare left to right, and the first differing position decides everything. So a change at an early index causes a huge jump, a change at a late index a tiny one. To land on the very next arrangement, keep the longest possible prefix untouched and edit as far right as you can.

It's the same instinct as incrementing an odometer: 129999 ticks the rightmost digits first, holding the high-order prefix as long as it can.

Pivot, swap, reverse

Set an array and step through. Phase 1 scans right-to-left, tinting the descending tail teal until it finds the pivot (the last rise). Phase 2 scans back for the smallest tail value greater than the pivot — the successor — and swaps. Phase 3 reverses the tail into ascending order.

Try 3 2 1 (no pivot → whole array reverses) or 1 3 2 (why you can't just swap the last two).

Prefix · pivot · maximal tail

Every array splits into three zones. The prefix stays frozen. The pivot is the one element that goes up. The tail after it is already descending — a maximal block — so it just needs flipping.

Choose the successor 3, swap it with the pivot, then minimize the tail:

Final: [1, 3, 1, 2, 4, 7]. The prefix never moved, the pivot rose by the least it could, and the tail is as small as it can be — the definition of "next."

Three arrays, three shapes

Row 2 is the instructive one: naively swapping the last two of [1,3,2] gives [1,2,3], which is smaller. The pivot is actually the 1, and reversing the tail afterward is what makes the result correct.

Three loops, one clean edge case

void nextPermutation(int[] nums) {
    int n = nums.length, i = n - 2;
    // 1. pivot: rightmost i with nums[i] < nums[i+1]
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        // 2. successor: rightmost value > pivot
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    // 3. reverse the tail (whole array if no pivot)
    reverse(nums, i + 1, n - 1);
}

O(N) time, O(1) space. Three sequential linear passes, all edits in-place. Sorting the tail would also work but costs O(N log N) — reversing exploits the structure that's already there.

Five ways it slips

Three facts that force the answer

Put together, the result is larger than the input (the pivot went up) and no valid permutation sits between them (the increase was minimal and the tail minimized). That's exactly "next." Duplicates don't break it — the strict > on the successor is what keeps the step honest.

Lexicographic greed: freeze, nudge, minimize

Array positions have descending importance — index 0 dominates everything after it. So the whole recipe is a priority game: preserve the high-priority prefix, make the smallest legal improvement, then minimize the low-priority remainder. The same three-beat move powers a family of problems.

The transferable move: when a problem asks for the next or smallest lexicographic result, don't enumerate — find the rightmost decision point, change it minimally, and rebuild the tail as small as possible.

Reconstruct it, don't memorize it

1. I need the smallest permutation larger than this one, so freeze as much left prefix as possible.
2. Scan right-to-left past the descending tail; the last rise is the pivot — the final place I can go up.
3. Swap the pivot with the smallest tail value strictly greater than it (first one hit scanning from the right).
4. The tail is still descending, so reverse it to make it ascending — the smallest tail for the new prefix.
5. No pivot at all? The array was the largest; reversing the whole thing wraps to the smallest.