31. Next Permutation

Two Pointer

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

        int left = n - 2;

        while (left >= 0) {
            if (nums[left] < nums[left + 1]) {
                // Step 1: find the first one that's greater than nums[left] (backwards)
                int j = n - 1;
                while (nums[j] <= nums[left]) {
                    j--;
                }

                // Step 2: swap nums[left] and nums[j]
                swap(nums, left, j);

                // Step 3: reverse left+1 to the end
                reverse(nums, left + 1, n - 1);
                return;
            }
            left--;
        }

        // reverse the whole array
        reverse(nums, 0, n - 1);
    }

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

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

1. TC: $O(n)$
2. Don’t forget to reverse the array after swap the number