31. Next Permutation leetcode solution in c++

Sure! Here is a response without any personal words or sentences at the beginning and end:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void nextPermutation(vector<int>& nums) {
    int n = nums.size();

    // Find the first decreasing element from the right side
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    // If no such element found, reverse the entire array
    if (i < 0) {
        reverse(nums.begin(), nums.end());
        return;
    }

    // Find the next greater element than nums[i] from the right side
    int j = n - 1;
    while (j > i && nums[j] <= nums[i]) {
        j--;
    }

    // Swap nums[i] with nums[j]
    swap(nums[i], nums[j]);

    // Reverse the elements from i+1 to the end
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    vector<int> nums = {1, 2, 3};
    nextPermutation(nums);

    for (int num : nums) {
        cout << num << " ";
    }

    return 0;
}

Explanation:

1. We start by finding the first decreasing element from the right side of the array nums. We iterate from n - 2 to 0 and stop at the first element i such that nums[i] < nums[i + 1] or until i < 0. This step helps us identify the element that needs to be changed in order to find the next permutation.

2. If we don't find any such element, it means the array is in descending order. In this case, we reverse the entire array because there is no greater permutation possible.

3. If we find an element i that is smaller than its next element, we need to find the next greater element than nums[i] from the right side of the array. We iterate from n - 1 to i + 1 and stop at the first element j such that nums[j] > nums[i].

4. We swap the elements nums[i] and nums[j] to get the next permutation. This ensures that the elements to the right of i are in descending order.

5. Finally, we reverse the elements from i + 1 to the end of the array to get the smallest possible permutation that is greater than the original array.

6. In the main function, we test the nextPermutation function with a sample input and print the result.

I hope this helps! Let me know if you have any further questions.