31. Next Permutation

📝 Problem Details

• Title: 31. Next Permutation
• Link: https://leetcode.com/problems/next-permutation/
• Difficulty: Medium
• Tags/Categories: Two-Pointers Arrays

permutation: an arrangement of its members into a sequence of linear order next permutation: the lexicographically next greater permutation of numbers meaning the smallest possible rearrangement that is strictly greater than the current order if no such permutation exists (i.e. the numbers are in descending order) return the smallest permutation by sorting in ascending order

input array nums find the next permutation of nums the replacement must be in-place (constant additional memory)

💡 Explanation of Solution

1. find the first decreasing element (pivot)
	- traverse from right to left
	- find the first index i such that nums[i] < nums[i+1]
		- this identifies the point where the order starts decreasing from the right
		- if no such i exists, the array is in descending order, so reverse it

2. find the next largest element and swap
	- find the smallest number larger than nums[i] on the right side
	- swap it with nums[i] to ensure we get the next larger permutation

3. reverse the right portion
	- since the right was initially in descending order, we reverse it to make it the smallest possible order

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), i = n - 2;
 
        // Step 1: Find the first decreasing element from the right
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
 
        if (i >= 0) { // If a valid pivot exists
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums[i], nums[j]); // Step 2: Swap
        }
 
        // Step 3: Reverse the right portion
        reverse(nums.begin() + i + 1, nums.end());  
    }
};