Next permutation

July 03, 2022 · 1 min read

https://leetcode.com/problems/next-permutation/

Find non-increasing sequence from right
Find just greater number from right
Swap them
Reverse from i to end

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

    while (i >= 0 && nums[i + 1] <= nums[i]) {
      i--;
    }

    if (i >= 0) {
      int j = nums.size() - 1;
      while (j >= 0 && nums[j] <= nums[i]) {
        j--;
      }
      swap(nums[i], nums[j]);
    }

    reverse(nums.begin() + i + 1, nums.end());
  }
};