Description:
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
- For example, for
arr = [1,2,3], the following are all the permutations ofarr:[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
- For example, the next permutation of
arr = [1,2,3]is[1,3,2]. - Similarly, the next permutation of
arr = [2,3,1]is[3,1,2]. - While the next permutation of
arr = [3,2,1]is[1,2,3]because[3,2,1]does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Examples:
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]Solution in Python:
To solve the problem of finding the next lexicographical permutation of an array of integers, we can follow these steps:
- Identify the rightmost pair where the order is increasing: Traverse the array from right to left and find the first pair of consecutive elements where the first element is smaller than the second. This will give us the rightmost “peak” in the array.
- Find the smallest element larger than the identified element: Once the rightmost pair is identified, find the smallest element to the right of the first element that is larger than it. This will be the element to swap with.
- Swap the elements: Swap the identified elements to ensure the next permutation is larger.
- Reverse the subarray to the right of the first element: After the swap, the subarray to the right of the first element will be in descending order. Reverse this subarray to get the smallest lexicographical order.
Python
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
# Step 1: Find the first decreasing element from the end
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0: # There is an element to be swapped
# Step 2: Find the element just larger than nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: Swap elements at i and j
nums[i], nums[j] = nums[j], nums[i]
# Step 4: Reverse the subarray from i+1 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
# Example usage:
# sol = Solution()
# nums = [1, 2, 3]
# sol.nextPermutation(nums)
# print(nums) # Output: [1, 3, 2]Explanation:
- Finding the first decreasing element:
- We iterate from the end of the array to the start and look for the first pair where
nums[i] < nums[i + 1]. This identifies the point where we can make a change to create a larger permutation.
- We iterate from the end of the array to the start and look for the first pair where
- Finding the element just larger than
nums[i]:- Starting from the end of the array, we find the smallest element that is larger than
nums[i]. This ensures that the next permutation is the smallest possible permutation that is larger than the current one.
- Starting from the end of the array, we find the smallest element that is larger than
- Swapping elements:
- We swap
nums[i]withnums[j], wherenums[j]is the element found in the previous step.
- We swap
- Reversing the subarray:
- To ensure that the permutation is the next lexicographical order, we reverse the subarray to the right of
ibecause this subarray is currently in descending order and needs to be in ascending order to get the smallest permutation.
- To ensure that the permutation is the next lexicographical order, we reverse the subarray to the right of
This approach ensures that we find the next permutation in place and with constant extra space, adhering to the problem constraints.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function(nums) {
let n = nums.length;
// Step 1: Find the first decreasing element from the end
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) { // There is an element to be swapped
// Step 2: Find the element just larger than nums[i]
let j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap elements at i and j
[nums[i], nums[j]] = [nums[j], nums[i]];
}
// Step 4: Reverse the subarray from i+1 to the end of the array
let left = i + 1;
let right = n - 1;
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
right--;
}
};
// Example usage:
let nums = [1, 2, 3];
nextPermutation(nums);
console.log(nums); // Output: [1, 3, 2]Solution in Java:
Java
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
// Step 1: Find the first decreasing element from the end
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) { // There is an element to be swapped
// Step 2: Find the element just larger than nums[i]
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap elements at i and j
swap(nums, i, j);
}
// Step 4: Reverse the subarray from i+1 to the end of the array
reverse(nums, i + 1, n - 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) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
solution.nextPermutation(nums);
System.out.println(Arrays.toString(nums)); // Output: [1, 3, 2]
}
}Solution in C#:
C#
public class Solution {
public void NextPermutation(int[] nums) {
int n = nums.Length;
// Step 1: Find the first decreasing element from the end
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) { // There is an element to be swapped
// Step 2: Find the element just larger than nums[i]
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap elements at i and j
Swap(nums, i, j);
}
// Step 4: Reverse the subarray from i+1 to the end of the array
Reverse(nums, i + 1, n - 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) {
while (start < end) {
Swap(nums, start, end);
start++;
end--;
}
}
}