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, 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. First, we check the last two digits 4, 1 to see if they 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 the new permutation to be as small as possible, we look from the back for the first number greater than 3, and we find 4.

Then, we swap the positions of 3 and 4, obtaining the sequence 4, 5, 3, 1. Because we need the newly generated sequence to be as small as possible, we can sort 5, 3, 1. It can be seen that in this algorithm, the trailing digits 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());
        }
};