# 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)