Next Permutation

Loading...LeetCode

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 of arr: [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.

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]

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

You can find the next permutation of an array by following these steps:

1. Start from the right end of the array and find the first element that is not in ascending order, let's call it i. If such element is not found, the array is in descending order, so reverse the entire array.

2. Find the smallest element to the right of i that is greater than the element at index i, let's call its index j.

3. Swap the elements at indices i and j.

4. Reverse the subarray starting from index i + 1 to the end of the array.

Here's how you can implement this in JavaScript:

function nextPermutation(nums) {
    // Find the first element from the right that breaks ascending order
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) {
        // Find the smallest element to the right of i that is greater than nums[i]
        let j = nums.length - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        // Swap nums[i] and nums[j]
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }

    // Reverse the subarray from i + 1 to the end
    let start = i + 1;
    let end = nums.length - 1;
    while (start < end) {
        [nums[start], nums[end]] = [nums[end], nums[start]];
        start++;
        end--;
    }
}

// Test cases
const nums1 = [1, 2, 3];
nextPermutation(nums1);
console.log(nums1); // Output: [1, 3, 2]

const nums2 = [3, 2, 1];
nextPermutation(nums2);
console.log(nums2); // Output: [1, 2, 3]

const nums3 = [1, 1, 5];
nextPermutation(nums3);
console.log(nums3); // Output: [1, 5, 1]

This implementation follows the steps described above to find the next lexicographically greater permutation in place.