Solution For Next Permutation

Problem:

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

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place, do not allocate extra memory.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1,5] Output: [1,5,1]

Example 4:

Input: nums = [1] Output: [1]

Solution:

The first step to solving the problem is to understand what is meant by lexicographically greater permutation.

A permutation is lexicographically greater if it appears after the given permutation when the permutations are arranged in the increasing order. For example, [3,2,1] is not lexicographically greater than [1,2,3] because it appears before it in the increasing order of permutations.

One way to find the next lexicographically greater permutation is to iterate through the array from right to left and find the first pair of adjacent elements where the left element is smaller than the right element. For example, in the array [1,2,5,4,3], the pair is (2,5) because 2 is smaller than 5.

Once we have found this pair of elements, we need to find the smallest element in the array that is greater than the left element of the pair. In the example above, the smallest element greater than 2 is 3.

Then, we swap the left element with this smallest element. After the swap, the array becomes [1,3,5,4,2].

Finally, we reverse the subarray starting from the right element of the pair (inclusive) to the end of the array. In the example above, the subarray is [5,4,2], and the reversed subarray becomes [2,4,5]. The final result is [1,3,2,4,5].

If we cannot find such a pair of adjacent elements, it means that the array is already in the lexicographically highest order, so we just reverse the entire array to get the lowest possible order.

Here’s the implementation of the above approach in Python:

class Solution:
def nextPermutation(self, nums: List[int]) -> None:
“””
Do not return anything, modify nums in-place instead.
“””
n = len(nums)
i = n – 2

    # Find the first pair of adjacent elements where the left element is smaller than the right element
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1

    if i >= 0:
        # Find the smallest element in the array that is greater than nums[i]
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1

        # Swap nums[i] and nums[j]
        nums[i], nums[j] = nums[j], nums[i]

    # Reverse the subarray starting from the right element of the pair
    # to the end of the array
    left, right = i+1, n-1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Time Complexity

The time complexity of the above approach is O(n), where n is the length of the input array.

Space Complexity

The space complexity of the above approach is O(1), as we are modifying the input array in place and not using any extra space.

Step by Step Implementation For Next Permutation

public class Solution {
    public void nextPermutation(int[] nums) {
        //find the first decreasing element from the end
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        //if found, swap with the element just greater than it
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        //reverse the elements after the found element
        reverse(nums, i + 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int start) {
        int end = nums.length - 1;
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

class Solution: 
    def nextPermutation(self, nums): 
        """ 
        :type nums: List[int] 
        :rtype: None 
        """ 
        # Find the largest index k such that nums[k] < nums[k + 1]. 
        # If no such index exists, just reverse nums and return 
        for k in range(len(nums) - 2, -1, -1): 
            if nums[k] < nums[k + 1]: 
                break 
        else: 
            nums.reverse() 
            return 
        
        # Find the largest index l > k such that nums[k] < nums[l]. 
        # Swap the elements nums[k] and nums[l] 
        for l in range(len(nums) - 1, k, -1): 
            if nums[k] < nums[l]: 
                break 
        nums[k], nums[l] = nums[l], nums[k] 
        
        # Reverse the sub-list starting at index next_permutation+1 to the end 
        nums[k + 1:] = nums[k + 1:][::-1]

var nextPermutation = function(nums) {
  // Find non-increasing suffix
  let i = nums.length - 1;
  while (i > 0 && nums[i - 1] >= nums[i])
      i--;
  if (i <= 0)
      return nums.reverse();
  
  // Find successor to pivot
  let j = nums.length - 1;
  while (nums[j] <= nums[i - 1])
      j--;
  let temp = nums[i - 1];
  nums[i - 1] = nums[j];
  nums[j] = temp;
  
  // Reverse suffix
  j = nums.length - 1;
  while (i < j) {
      temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
      i++;
      j--;
  }
  return nums;
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include  #include  using namespace std ; void nextPermutation ( vector < int > & nums ) { int n = nums . size ( ) ; int i = n - 2 ; while ( i >= 0 && nums [ i ] >= nums [ i + 1 ] ) { i -- ; } if ( i >= 0 ) { int j = n - 1 ; while ( j >= 0 && nums [ j ] <= nums [ i ] ) { j -- ; } swap ( nums [ i ] , nums [ j ] ) ; } reverse ( nums . begin ( ) + i + 1 , nums . end ( ) ) ; } int main ( ) { vector < int > nums { 1 , 2 , 3 } ; nextPermutation ( nums ) ; for ( int num : nums ) { cout << num << " " ; } cout << endl ; return 0 ; }

public class Solution {
    public void NextPermutation(int[] nums) {
        // Find the first element from the right that is smaller than the element to its right
        int i = nums.Length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }

        // If no such element exists, then the array is sorted in descending order and we are done
        if (i >= 0) {
            // Find the first element from the right that is greater than the element at index i
            int j = nums.Length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }

            // Swap the elements at indices i and j
            Swap(nums, i, j);
        }

        // Reverse the subarray starting at index i + 1
        Reverse(nums, i + 1);
    }
    
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void Reverse(int[] nums, int start) {
        int i = start;
        int j = nums.Length - 1;
        while (i < j) {
            Swap(nums, i, j);
            i++;
            j--;
        }
    }
}