LeetCode 31 – Next Permutation | Love Me Some Coding

Next Permutation is a problem you either see or you do not. There is no data structure to reach for and no recursion — just three passes over the array, in the right order, for reasons that take a minute to work out and are obvious afterwards. It is worth doing that minute of work, because the same shape underlies every "generate permutations in order" question.

The problem

Rearrange the numbers into the next lexicographically greater permutation, in place and in constant extra memory. If no greater permutation exists, rearrange into the smallest one — ascending order.

[1, 2, 3] -> [1, 3, 2]
[1, 3, 2] -> [2, 1, 3]     not [3, 1, 2] — the NEXT one, not just any greater one
[3, 2, 1] -> [1, 2, 3]     already the largest, so wrap around
[1, 1, 5] -> [1, 5, 1]     duplicates are allowed
[1]       -> [1]

Where the answer lives

Start from the observation that a descending suffix is already maximal. If the array ends in […, 9, 7, 4, 2], no rearrangement of just those four values produces anything larger — they are already in their biggest order. So the change has to reach further left than the descending suffix goes.

That gives the first step. Scan from the right while each element is >= its neighbour, and stop at the first element that is smaller than the one after it. Call it the pivot. Everything to the pivot's right is non-increasing, and the pivot is the only position where an increase is possible.

If the scan runs off the left end there is no pivot: the whole array is descending, it is the largest permutation, and the answer is to reverse the whole thing. That case needs no separate branch, as the code below shows.

The two remaining steps

Swap the pivot with the smallest value to its right that still beats it. The result has to be greater, so the pivot must increase; it has to be the next one, so it must increase as little as possible. Because the suffix is non-increasing, scanning it from the right finds that value immediately — the first element exceeding the pivot is the smallest one that does.

Then reverse the suffix. After the swap the prefix is finally larger, so the suffix should be as small as possible. It is still non-increasing (swapping in a value that sits between its neighbours preserves that), so reversing turns it into non-decreasing — the smallest arrangement of those values, in O(n) and without sorting.

[1, 5, 8, 4, 7, 6, 5, 3, 1]
        ^pivot=4 at index 3 — first element smaller than its right neighbour

              suffix [7, 6, 5, 3, 1] is non-increasing
              smallest value in it that beats 4, scanning from the right: 5

[1, 5, 8, 5, 7, 6, 4, 3, 1]     after the swap
[1, 5, 8, 5, 1, 3, 4, 6, 7]     after reversing the suffix

Java

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;

        // 1. First index from the right that breaks the non-increasing run.
        int pivot = n - 2;
        while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) {
            pivot--;
        }

        // 2. Swap it with the smallest value to its right that is still larger.
        //    Skipped entirely when pivot == -1: the array is fully descending.
        if (pivot >= 0) {
            int swap = n - 1;
            while (nums[swap] <= nums[pivot]) {
                swap--;
            }
            swap(nums, pivot, swap);
        }

        // 3. The suffix is non-increasing; reversing makes it the smallest.
        //    With pivot == -1 this reverses the whole array, which is the wrap-around.
        reverse(nums, pivot + 1, n - 1);
    }

    private void reverse(int[] nums, int lo, int hi) {
        while (lo < hi) {
            swap(nums, lo++, hi--);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

The no-pivot case falls out of the arithmetic rather than needing an if: when pivot is -1, step 2 is skipped and step 3 reverses [0, n - 1], which is exactly the required wrap to ascending order.

The inner search in step 2 needs no bounds check. The pivot is strictly less than nums[pivot + 1], so at least one element to its right exceeds it and the loop always terminates before running off the array.

Python

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        n = len(nums)

        pivot = n - 2
        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1

        if pivot >= 0:
            swap = n - 1
            while nums[swap] <= nums[pivot]:
                swap -= 1
            nums[pivot], nums[swap] = nums[swap], nums[pivot]

        nums[pivot + 1:] = reversed(nums[pivot + 1:])

The slice assignment happens to handle pivot == -1 correctly too: nums[0:] is the whole list. Note this modifies in place as the problem requires — rebinding nums = ... would leave the caller's list untouched.

The role of the comparison operators

Both loops use non-strict comparisons, and both are load-bearing when values repeat:

nums[pivot] >= nums[pivot + 1] keeps scanning past equal neighbours. A run of equal values is still maximal — there is nothing to gain by stopping inside it.
nums[swap] <= nums[pivot] skips values equal to the pivot. Swapping the pivot with an equal value changes nothing, and the result would not be a greater permutation at all.

[1, 1, 5] is the input that exercises both. Getting either operator strict returns the array unchanged.

Complexity

O(n) time — three passes, each visiting each element at most once — and O(1) space, which the problem explicitly demands. Generating all permutations and sorting them is O(n! · n) and does not fit in memory past about eleven elements; do not offer it as a starting point beyond a single sentence.

What the interviewer is checking

That you find the pivot from the right, and can say why a descending suffix is already maximal.
That the swap partner is the smallest value greater than the pivot, and that scanning from the right finds it for free.
That you reverse the suffix rather than sorting it — same result, O(n) instead of O(n log n).
The fully-descending input, and that it needs no special case.
Duplicates. [1, 1, 5] and [2, 2, 2] both go wrong with strict comparisons.
That the array is modified in place.