Next permutation problem

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).