Thinking process

https://discuss.leetcode.com/topic/14124/sharing-my-clean-and-easy-understand-java-code-with-explanation

https://discuss.leetcode.com/topic/2542/share-my-o-n-time-solution

1. find the first pair of numbers from the tail that the left is smaller than the right
2. find the first number from the tail that is larger than the left number, and then swap
3. sort the numbers on the right, to make the rest as small as possible

Mistakes

1. out of boundary
2. how to sort the remaining elements

public class Solution {
    public void nextPermutation(int[] nums) {
        int inputLen = nums.length;

        if (inputLen <= 1) return;

        int left = inputLen - 2, right = inputLen - 1;
        while (left >= 0 && nums[left] >= nums[right]) {
            left--;
            right--;
        }

        if (left < 0) {
            sort(nums, left + 1, inputLen - 1);
            return;
        }

        for (int i = inputLen - 1; i >= 0; --i) {
            if (nums[i] > nums[left]) {
                right = i;
                break;
            }
        }

        //swap
        swap(nums, left, right);

        //sort numbers on the right of left pointer
        sort(nums, left + 1, inputLen - 1);


    }

    private void swap(int[] nums, int pos1, int pos2) {
        int tmp = nums[pos1];
        nums[pos1] = nums[pos2];
        nums[pos2] = tmp;
    }

    private void sort(int[] nums, int start, int end) {
        if(start > end) return;
        for (int i = start; i <= (end + start) / 2; ++i) {
            swap(nums, i, start + end - i);
        }
    }
}