Gokking #25255

class Solution {
    public void nextPermutation(int[] nums) {
        int i = -1;

        // 1. find last increasing pair
        for (int j = 0; j < nums.length - 1; j++) {
            if (nums[j] < nums[j + 1]) {
                i = j;
            }
        }
        if (i == -1) {
            reverse(nums, 0);
            return;
        }

        // 2. from i + 1, find last k, that nums[k] > nums[i];
        int k = i + 1;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] > nums[i]) {
                k = j;
            }
        }

        swap(nums, i, k);

        // 3. reverse from i + 1 to end
        reverse(nums, i + 1);
    }

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

    void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;

        while (i < j) {
            swap(nums, i++, j--);
        }
    }
}