aboutsummaryrefslogtreecommitdiff
path: root/next_permutation.cpp
blob: 95e70f46df121bb564f59b5ad93a9b71d2fbdbe9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#include <vector>
using namespace std;

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 (nums[j] <= nums[i])
        j--;
      swap(nums, i, j);
    }
    reverse(nums, i + 1);
  }

private:
  void reverse(vector<int> &nums, int start) {
    int i = start, j = nums.size() - 1;
    while (i < j) {
      swap(nums, i, j);
      i++;
      j--;
    }
  }

  void swap(vector<int> &nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
};

int main() {}