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--; } } }