29. Next Permutation

Scan from the right for the first descent (the pivot). Swap it with the smallest element to its right that is still larger, then reverse the suffix to make it as small as possible.

Three steps

1. Find the pivot: the rightmost index i with nums[i] < nums[i+1]. Everything after i is non-increasing (already the largest arrangement).
2. Swap: find the rightmost j with nums[j] > nums[i] and swap them — the smallest possible increase at position i.
3. Reverse the suffix after i to turn it from descending (largest) into ascending (smallest).

If no pivot exists, the array is the last permutation → reverse the whole thing.

Worked example

[1,2,3] → pivot at index 1 (2<3), swap 2 and 3 → [1,3,2], suffix already minimal → [1,3,2]. [3,2,1] → no pivot → reverse → [1,2,3].

Complexity

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

class Solution {
    public int[] nextPermutation(int[] nums) {
        int n = nums.length, 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--;
            int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
        }
        for (int l = i + 1, r = n - 1; l < r; l++, r--) {
            int t = nums[l]; nums[l] = nums[r]; nums[r] = t;
        }
        return nums;
    }
}