Code Implementation

class Solution:
    def nextPermutation(self, nums):
        # Step 1: Find the first decreasing element from the end
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        # Step 2: If found, find just larger element to swap
        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # Step 3: Reverse the elements after i
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
      

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.size() - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};
      

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}
      

var nextPermutation = function(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};
      

Problem Description

Given an array of integers nums representing a permutation of numbers, rearrange nums into its next lexicographically greater permutation. If such an arrangement is not possible (i.e., the array is sorted in descending order), rearrange it as the lowest possible order (i.e., sorted in ascending order).

• The replacement must be in-place and use only constant extra memory.
• Return nothing; instead, modify nums directly.
• There is always exactly one valid answer for each input.
• Do not reuse elements; each element must appear exactly once.

For example, given nums = [1,2,3], the next permutation is [1,3,2]. If nums = [3,2,1], the next permutation is [1,2,3].

Thought Process

At first glance, the problem looks like it might require generating all permutations and then picking the next one in order. However, this would be extremely inefficient, especially for large arrays. The brute-force approach would involve generating all possible permutations, sorting them, and returning the next one, which is computationally expensive.

Instead, we look for a more efficient way to find the next permutation in-place, without generating all possibilities. By examining the properties of permutations, we realize that we need to modify the array minimally to get the next lexicographically greater order. This involves finding the right place to swap two elements so that the result is just larger than the current arrangement, and then arranging the remaining elements in the smallest possible order.

This shift from generating all permutations to making the minimal change possible is the key insight for an optimal solution.

Solution Approach

The optimal algorithm to find the next permutation works as follows:

1. Find the first decreasing element from the end:
   • Start from the end of the array and look for the first index i such that nums[i] < nums[i + 1].
   • This identifies the point where the order can be increased.
2. Find the element just larger than nums[i] to its right:
   • Again, scan from the end to find an index j such that nums[j] > nums[i].
   • This is the smallest number greater than nums[i] to swap with.
3. Swap nums[i] and nums[j]:
   • This increases the permutation as little as possible.
4. Reverse the subarray to the right of i:
   • To get the next smallest lexicographical order, reverse the subarray from i + 1 to the end.
   • This ensures the tail is in ascending order, making the permutation minimal.
5. If no such i exists:
   • The array is in descending order. Simply reverse the whole array to get the smallest permutation.

This approach uses only a few pointers and swaps, making it both time and space efficient.

Example Walkthrough

Let's walk through the algorithm with an example:

Input: nums = [1, 2, 3, 6, 5, 4]

1. Find first decreasing element from the end:
   Scan from right to left: 4 < 5 (no), 5 < 6 (no), 6 > 3 (yes). So, i = 2 (nums[2] = 3).
2. Find element just larger than 3 to its right:
   Starting from the end, 4 > 3 (yes), so j = 5.
3. Swap nums[2] and nums[5]:
   Array becomes [1, 2, 4, 6, 5, 3]
4. Reverse subarray from index 3 to end:
   Reverse [6, 5, 3] to [3, 5, 6]. Final array is [1, 2, 4, 3, 5, 6].

This is the next lexicographical permutation after [1, 2, 3, 6, 5, 4].

Time and Space Complexity

• Brute-force: Generating all permutations would take O(n!) time and O(n) space for each permutation, which is not feasible for large n.
• Optimized approach:
  • Time Complexity: O(n), since each step (finding the pivot, finding the swap point, and reversing) takes at most O(n) time.
  • Space Complexity: O(1), as all operations are done in-place with only a few variables.

Summary

The "Next Permutation" problem challenges us to rearrange an array into its next lexicographical order efficiently and in-place. By identifying the right pivot and swap points and reversing the correct subarray, we can achieve this in linear time and constant space. The elegance of the solution lies in its simplicity and minimal change to the original array, ensuring the next permutation is always found with the least amount of work.