LC 31

Goal:
Given an array of non-negative integers, find the lexicographically next permutation. If no such permutation, return the ascending order permutation.

Intuition:
1. Notice that non-increasing sequence does not have next greater permutation, and non-decreasing sequence is the smallest permutation.
2. we want to find the permutation is as little lexicographically greater as possible than current one, thus the position changed should be as right-side as possible.

Algorithm:
1. Find the first position, pos , that starts to increase from back of the array so that the subarray [pos+1: ] is a non-increasing sequence meaning that it does not have next greater permutation, thus pos is the right-most position that starts to have permutation.
2. Starts from pos+1, find the last position j, with value greater than [pos], and swap(pos, j). As we mentioned, [pos+1: ] is a non-increasing sequence, we swap [pos] and [j] will not break the characteristic.
3. Reverse the subarray [pos+1: ] in place. FYI, [pos+1: ] is a non-increasing sequence or in other words, the subarray is sorted in descending order, thus you can swap both ends to reverse the subarray.

Time: O(size of input)