# Share my clean short O(n) solution with comments and example

• class Solution {

public:

``````void nextPermutation(vector<int>& nums) {
int i = nums.size() - 1;
while(i > 0) {
if (nums[i] > nums[i-1]) { /* search the first element from the back that is not in descending order, which is nums[i-1] */
int j = nums.size()-1;
while(nums[i-1] >= nums[j]) j--; /* search the first element from the back in the range (nums[i], nums[nums.size()-1] that is larger than num[i-1] */
swap(nums[i-1], nums[j]); /* swap the two elements we just found */
break;
}
i--;
}
reverse(nums.begin()+i, nums.end()); /* this range should be in increasing order */
}
``````

};

Let's look at an example:

[5, 8, 21, 15, 10, 6]

first, find 8;

then, find 10 from [21, 15, 10, 6] that is larger than 8 and is closest to the end;

swap, to [5, 10, 21, 15, 8, 6];

finally, the range [21, 15, 8, 6] needs to be in increasing order as [6, 8, 15, 21], we got [5, 10, 6, 8, 15, 21].

• Awesome explanation. Thanks

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.