LeetCode Hot 100 P31 Next Permutation

---

Timeline

Timeline

2026-03-17

init

Two pointers

---

Problem:

P31 Next Permutation

https://leetcode.cn/problems/next-permutation/description/?envType=study-plan-v2&envId=top-100-liked

For example, for the permutation 2, 6, 3, 5, 4, 1, we want to find the next permutation that is just larger than it. So we can look from the back to the front. First, we check whether the last two digits 4, 1 can form a larger permutation; the answer is no. Similarly, 5, 4, 1 also cannot. Until we reach the permutation 3, 5, 4, 1, because 3 < 5, we can rearrange this segment of numbers to get the next permutation.

Because we need to make the new permutation as small as possible, we look from the back to the front for the first number greater than 3, and find that it is 4.

Then, we swap the positions of 3 and 4, obtaining the sequence 4, 5, 3, 1. Because we need to make the newly generated sequence as small as possible, we can sort 5, 3, 1. We can see that in this algorithm, the trailing numbers we get are always in descending order, so we only need to reverse them.

Finally, we get the sequence 4, 1, 3, 5, and the complete sequence is 2, 6, 4, 1, 3, 5.

#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
        void nextPermutation(vector<int> &nums)
        {
                int i, n = nums.size();
                int pos = -1;

                for (i = n - 2; i >= 0; i--) {
                        if (nums[i] < nums[i + 1]) {
                                pos = i;
                                break;
                        }
                }
                
                if (pos != -1) {
                        for (i = n - 1; i >= 0; i--) {
                                if (nums[i] > nums[pos]) { // Find the first number greater than nums[pos] and swap.
                                        std::swap(nums[i], nums[pos]);
                                        break;
                                }
                        }
                }

                std::reverse(nums.begin() + pos + 1, nums.end());
        }
};