Next Permutation

How it works

To find the next lexicographically greater permutation, we need to make the smallest possible change that increases the array's value. The key insight is to find the rightmost position where we can make an increase.

Scan from right to left to find the first element that is smaller than its right neighbor. This element (call it pivot) can be swapped with something larger to get a bigger permutation. We then find the smallest element to the right of pivot that is still larger than pivot and swap them.

After the swap, everything to the right of the pivot position is in descending order. To get the smallest possible permutation from this point, we reverse that suffix to ascending order.

If no such pivot exists (the array is fully descending), we are at the largest permutation, so we reverse the entire array to get the smallest.

Steps

1. Scan from the second-to-last element leftward to find the first index i where nums[i] < nums[i+1].
2. If such an index exists:
   • Scan from the right to find the first index j where nums[j] > nums[i].
   • Swap nums[i] and nums[j].
3. Reverse the subarray from i+1 to the end.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Finding Pivot with Wrong Comparison

The pivot is the rightmost element that is smaller than its right neighbor (nums[i] < nums[i+1]). Using <= instead of < causes the algorithm to fail on arrays with duplicate elements, as it may skip valid pivot positions.

Swapping with Wrong Element

After finding the pivot, you must swap it with the smallest element to its right that is still larger than the pivot. Swapping with the first larger element from the left (instead of from the right) may not produce the lexicographically smallest increase.

Forgetting to Reverse the Suffix

After swapping, the suffix to the right of the pivot position is in descending order. Failing to reverse it to ascending order produces a larger permutation than necessary. The reversal is essential to get the next (smallest) greater permutation.

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        l, r = i + 1, n - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        int l = i + 1, r = n - 1;
        while (l < r) {
            swap(nums[l++], nums[r--]);
        }
    }
};