Next Permutation Solution.

Brute Force

steps:-

1. Generate all the permutations using recursion.
2. Sort them.
3. Find the index of the nums array from all the permutations.
4. return the next permutation from this index as the answer

class Solution {
public:
    void findPermute(int index, vector<int>& nums, vector<vector<int>>&res){
        if(index==nums.size()){
            // one permutation is complete
            res.push_back(nums);
            return;
        }
        for(int i=index;i<nums.size();i++){
            swap(nums[index],nums[i]);
            findPermute(index+1,nums,res);
            swap(nums[index],nums[i]);
        }
    }
    void nextPermutation(vector<int>& nums) {
        vector<vector<int>>res;
        findPermute(0,nums,res);
        set<vector<int>> s; // to store all permutation in sorted order
        for(int i=0;i<res.size();i++){
            s.insert(res[i]);
        }
        for (auto itr = s.begin(); itr != s.end(); itr++) {
            if(*itr==nums && itr==(--s.end())) // if last permutation is nums then return the first permutation according to the problem (edge case).
                nums = *(s.begin());
            else if(*itr==nums)
            {
                itr++;
                nums=*itr;
                break;
            }
        }
    }
};        

Explanation of code:-

findPermute Function: Purpose: To recursively generate all permutations of the array nums.

Logic:

If index == nums.size(),

a complete permutation is generated, so add nums to the result res.

Otherwise, iterate over all possible elements that can be placed at the index. Swap the current element with each element from the index onwards.

Call findPermute recursively for the next index. Backtrack by swapping the elements back to restore the original order.

nextPermutation Function:

Purpose: To find the next permutation of nums in lexicographical order.

Logic:

Call findPermute to generate all permutations of nums and store them in res.

Use a set to store all unique permutations in sorted order. This ensures permutations are in lexicographical order, as set automatically sorts elements. Traverse the set to for current permutation (nums): If nums matches the current permutation in the set and it's the last element, wrap around to the first permutation in the set. Otherwise, move to the next permutation in the set.

Time Complexity:- O(n!?log(n!))

Space Complexity:- O(n?n!)

STL

use next_permutation(arr.begin(),arr.end());

Optimised Approach

• Start from the end of the array and find the first element nums[i] such that nums[i] < nums[i+1]. Call this the "pivot".
• If no such i exists, reverse the array (as the current permutation is the last one in lexicographical order).
• Otherwise, find the smallest element nums[j] to the right of the pivot that is larger than nums[i].
• Swap nums[i] and nums[j].
• Reverse the elements to the right of i to get the next permutation.

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), i, j;
        // Step 1: Find the pivot
        for (i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) break;
        }
        if (i < 0) {
            // Step 2: If no pivot, reverse the array
            reverse(nums.begin(), nums.end());
        } else {
            // Step 3: Find the next larger element to swap
            for (j = n - 1; j > i; j--) {
                if (nums[j] > nums[i]) break;
            }
            swap(nums[i], nums[j]);
            // Step 4: Reverse the elements to the right of the pivot
            reverse(nums.begin() + i + 1, nums.end());
        }
    }
};        

For better understanding watch this video: Youtube.