LeetCode 31. Next Permutation

public class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int i = start;
        int j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

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

We iterate through nums from right to left to find the number nums[i] where the descending order occurs for the first time. Then we scan through the nums from right to i+1 to find a number that is greater nums[i] and swap the number with it. Finally, we reverse nums[i+1] ... nums[nums.length-1].

By doing so, we can guarantee that:

1. The next permutation is always greater or equal to the current permutation (we assume the numbers in the current permutation are not sorted in descending order).
2. There does not exist a permutation that is greater than the current permutation and smaller than the next permutation generated by the above code.
3. If the numbers in the current permutation are already sorted in descending order (i.e. greatest possible value), the next permutation has the smallest value.

Time Complexity: O(n)

Extra Space: O(1)