Given an array of number rearrange the given numbers into the lexicographic-ally next greater permutation of itself.
Example
Input: 1,2,3 3,2,1 1,1,5 Output: 1,3,2 1,2,3 1,5,1
Next permutation solution in javascript
This problem is similar of finding the next greater element, we just have to make sure that it is greater lexicographic-ally.
Theoretically this is how the solution works.
- Find the first index from the end where the value is less than the next value, if no such value exists then mark the index as -1.
- Next find the next greater element from the rear before the first index.
- Swap both the elements.
- Reverse everything in the array before the first index that was found, if the index is -1 then whole array will be reversed.
- Thus next permutation is formed.
const nextPermutation = (nums) => { let i, j; // Find the first index from the right where the value is less than the next value. If this doesn't exist then i = -1. for (i = nums.length - 2; nums[i] >= nums[i + 1] && i >= 0; i--); if (i >= 0) { // Find the first index from the right where the value is greater than the value found in previous step. for (j = nums.length - 1; nums[j] <= nums[i]; j--); // Swap the two values found. [nums[i], nums[j]] = [nums[j], nums[i]]; } // Reverse everything after index i found above. Note if i = -1 then the whole array is reversed. for (i++, j = nums.length - 1; i < j; i++, j--) { [nums[i], nums[j]] = [nums[j], nums[i]]; } }; Input: const arr = [1, 1, 5]; nextPermutation(arr); console.log(arr); Output: [1, 5, 1]
Time complexity: O(n ^ 2).
Space complexity: O(1).