If no greater permutation exists, the array should be rearranged into its lowest possible order.
Problem
Given an array of integers nums, rearrange the numbers into the lexicographically next greater permutation of numbers.If such an arrangement is not possible, rearrange the array into the lowest possible order by sorting it in ascending order.
The rearrangement must be performed in-place and use only constant extra space.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1, 2, 3]Output
[1, 3, 2]Solution
This solution uses a combination of the Two Pointer technique and Array Manipulation. The key idea is to find the first position from the right where the current element is smaller than the element immediately after it. This position is called the pivot.We scan the array from right to left to find the pivot. Once the pivot is found, we scan from the right again to find the smallest element greater than the pivot and swap them.
After the swap, the elements after the pivot are still arranged in descending order. To obtain the smallest permutation greater than the original one, we reverse this suffix into ascending order.
If no pivot is found, the entire array is in descending order, which means it is already the largest possible permutation. In this case, we simply reverse the entire array to obtain the smallest permutation.
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
// Find the first decreasing element from the right.
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// If a pivot exists, find the next greater element.
if (i >= 0) {
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
// Reverse the suffix.
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 i, int j) {
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
}Complexity
The array is traversed from right to left to find the pivot, and the remaining suffix is traversed to find the next greater element and reverse the suffix. Therefore, the time complexity isO(n).
The array is modified in-place and the algorithm uses only a few variables, so the extra space complexity is
O(1).