# [Concise C++] Easy idea with clear explanation

• ``````class Solution {
public:
void nextPermutation(vector<int>& nums) {
int end = nums.size() - 1, start = end - 1;
for ( ; start >= 0 && nums[start] >= nums[start + 1]; --start) ;

if (start == -1) {
reverse(nums.begin(), nums.end());
return ;
} else {
int minidx = start + 1;
for ( ; minidx + 1 < nums.size(); ++minidx) {
if (nums[minidx + 1] <= nums[start]) break;
}
swap(nums[start], nums[minidx]);
sort(nums.begin() + (start + 1), nums.end());
return ;
}
}
};
``````

Given array : [1, 3, 2, 4, 9, 8, 7, 6, 5]

• As you can find, the last five elements are in reverse order [1, 3, 2, 4, | 9, 8, 7, 6, 5].
• Which means, if the given array is [9, 8, 7, 6, 5], then it is already the last permutation of these five elements, we cannot "increase" it anymore.
• Then we should find the least significant number of the remaining array. Among the first four numbers, [1, 3, 2, 4], the least significant number is always on the last position of this array, and it's 4 (nums[3]).
• Then this problem is reduced to find the next permutation of [4, | 9, 8, 7, 6, 5]. Because we'll never need to touch the first three numbers to get the next permutation.
• Because 4 (nums[3]) is on the least significant position, and [9, 8, 7, 6, 5] cannot be any larger. To get the next permutation, we need to "increase" nums[3] by the smallest possible step and "decrease" the nums[4:8] to its "smallest" permutation.
• To get the smallest "increase" on nums[3], we need to find the smallest element in [9, 8, 7, 6, 5] that is larger than nums[3]. After swapping these two number, we need to decrease nums[4:8] to the smallest, a.k.a. in the sorted order.

The steps are:
[1, 3, 2, 4, | 9, 8, 7, 6, 5]
--> [1, 3, 2, |4, 9, 8, 7, 6, 5]
--> [1, 3, 2, |4, 9, 8, 7, 6, 5]
--> [1, 3, 2, |5, 9, 8, 7, 6, 4]
--> [1, 3, 2, 5, |9, 8, 7, 6, 4]
--> [1, 3, 2, 5, |4, 6, 7, 8, 9]

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