Next Permutation
Implement a function that generates the next lexicographically greater permutation of a given array of integers. If no greater permutation exists, return the first permutation (i.e., the array sorted in ascending order).
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
Examples:
Input: [1,2,3]
Output: [1,3,2]
Explanation: The next lexicographically greater permutation of [1,2,3] is [1,3,2].
Input: [3,2,1]
Output: [1,2,3]
Explanation: Since [3,2,1] is the last permutation, the next permutation is the first permutation, which is [1,2,3].
Solutions
Two Pointers
The approach is to find the first pair of elements from the right that are in increasing order. If no such pair exists, the array is the last permutation. Otherwise, we swap the first element with the smallest element to its right that is greater than it, and then reverse the elements to the right of the first element.
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;
int right = nums.length - 1;
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}Follow-up:
What if the input array contains duplicate elements?
