Next Permutation

Given an array of integers arr[] representing a permutation, implement the next permutation that rearranges the numbers into the lexicographically next greater permutation. If no such permutation exists, rearrange the numbers into the lowest possible order (i.e., sorted in ascending order). 

Note – A permutation of an array of integers refers to a specific arrangement of its elements in a sequence or linear order.

Examples:

Input: arr = [2, 4, 1, 7, 5, 0]
Output: [2, 4, 5, 0, 1, 7]
Explanation: The next permutation of the given array is {2, 4, 5, 0, 1, 7}.

Input: arr = [3, 2, 1]
Output: [1, 2, 3]
Explanation: As arr[] is the last permutation, the next permutation is the lowest one.

Input: arr = [3, 4, 2, 5, 1]
Output: [3, 4, 5, 1, 2]
Explanation: The next permutation of the given array is {3, 4, 5, 1, 2}.

Constraints:
1 ≤ arr.size() ≤ 10⁵
1 ≤ arr[i] ≤ 10⁵

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
 public:
  vector<int> nextPermutation(vector<int>& nums) {
    int pivotIndex = -1;

    // Find the rightmost element that is smaller than its next element
    for (int i = nums.size() - 2; i >= 0; --i) {
      if (nums[i] < nums[i + 1]) {
        pivotIndex = i;
        break;
      }
    }

    if (pivotIndex == -1) {  // If no such element is found, reverse the array
      reverse(nums.begin(), nums.end());
      return nums;
    }

    // Find the rightmost element larger than the pivot
    for (int i = nums.size() - 1; i > pivotIndex; --i) {
      if (nums[i] > nums[pivotIndex]) {
        swap(nums[pivotIndex], nums[i]);  // Swap
        break;
      }
    }

    // Reverse the elements after the pivot index
    reverse(nums.begin() + pivotIndex + 1, nums.end());
    return nums;
  }
};

class Solution:
    def nextPermutation(self, nums):
        pivotIndex = -1

        # Find the rightmost element that is smaller than its next element
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                pivotIndex = i
                break

        if pivotIndex == -1:  # If no such element is found, reverse the list
            nums.reverse()
            return nums

        # Find the rightmost element larger than the pivot
        for i in range(len(nums) - 1, pivotIndex, -1):
            if nums[i] > nums[pivotIndex]:
                nums[pivotIndex], nums[i] = nums[i], nums[pivotIndex]  # Swap
                break

        # Reverse the elements after the pivot index
        nums[pivotIndex + 1:] = nums[pivotIndex + 1:][::-1]
        return nums

Time Complexity

• Finding the Pivot Index:

  The algorithm iterates from right to left to find the first element that is smaller than its next element. This operation takes \( O(n) \), where n is the size of the array.

• Finding the Element to Swap:

  Once the pivot index is found, the algorithm iterates from the end to find the smallest element larger than the pivot. This operation also takes \( O(n) \) in the worst case.

• Reversing the Subarray:

  The subarray after the pivot index is reversed. This operation takes \( O(n) \) in the worst case.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), as all operations are linear and performed sequentially.

Space Complexity

• In-Place Modifications:

  The algorithm modifies the input array nums in place without requiring additional data structures.

• Auxiliary Variables:

  Only a few auxiliary variables (pivotIndex, i) are used, which require \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).