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

        while(i >= 0){
            if(nums[i] < nums[i + 1]) break;
            i--;
        }

        if(i >= 0){
            int j = n - 1;
            while(nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }

        reverse(nums, i + 1, n - 1);
    }

    void reverse(int[] nums, int l, int r){
        while(l < r){
            swap(nums, l++, r--);
        }
    }

    void swap(int[] nums, int x, int y){
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}