Next Permutation medium

Problem Statement

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is impossible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Example 1

Input: nums = [1,2,3] Output: [1,3,2]

Example 2

Input: nums = [3,2,1] Output: [1,2,3]

Steps and Explanation

The algorithm involves finding the first digit from the right that is smaller than its right neighbor. This digit is the pivot. Then, we find the smallest digit to the right of the pivot that is greater than the pivot. We swap these two digits. Finally, we reverse the subarray to the right of the pivot to get the lexicographically next greater permutation.

1. Find the pivot: Iterate from the right end of the array. The pivot is the rightmost digit that is smaller than its right neighbor. If no such digit is found, the array is already in descending order, and we simply reverse the entire array.

2. Find the successor: Find the smallest digit to the right of the pivot that is greater than the pivot.

3. Swap: Swap the pivot and the successor.

4. Reverse: Reverse the subarray to the right of the pivot. This ensures that the remaining digits are in ascending order, creating the next permutation.

Code (C++)

#include <algorithm>
#include <vector>

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

        // Find the pivot
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // If the array is already in descending order, reverse it
        if (i < 0) {
            std::reverse(nums.begin(), nums.end());
            return;
        }

        // Find the successor
        int j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }

        // Swap the pivot and successor
        std::swap(nums[i], nums[j]);

        // Reverse the subarray to the right of the pivot
        std::reverse(nums.begin() + i + 1, nums.end());
    }
};

Complexity

• Time Complexity: O(n), where n is the length of the input array. This is because we iterate through the array at most three times (finding the pivot, finding the successor, and reversing the subarray).
• Space Complexity: O(1). The algorithm operates in-place, using only constant extra space.