31. Next Permutation

Next Permutation

Problem Description 

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 an arrangement is not possible, the array must be rearranged in 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

Approach) Native

Idea:

Changes made to the left part of an array have more impact on the lexicographical sorting than changes made to the right side, so logically, in order to find the next permutation that is lexicographically greater, we need to find the farthest right-most number that can be swapped for a larger number. Also, the larger number must come from the target number's right, otherwise, you'd create a permutation that is lexicographically lower.

We also then need to make sure that it's not just any larger number, but the next possible larger number from the numbers to its right. Then, we'll need to make sure that the remaining numbers to the right of our swapped target are in their lexicographically smallest configuration. (Think of it like a counter rolling over from 0999 into 1000.)

Implementation:

So the first order of business is to find the target number we want to swap. As we check from the right to the left, if each number is larger than the one before, then we clearly can't find a lexicographically larger number. Therefore, we have to move left until we find the first time a number is lower than the number to its right.

Once we find that target (N[i]), the very important thing to recognize is that the numbers to the target's right are already in sorted order, just in reverse order, so we can easily reverse them. (Even if we don't actually find the target, we still want to reverse the entire array, per the instructions.)

It's easy then to move from the smallest to largest of the reversed numbers and look for the first number (N[j]) that's larger than our target so that we can swap the two. Since N[j] is lexicographically nearest to N[i], the subarray to the right of N[i] will still be in the correct order even after the swap.

A simple helper functions to swap array elements will be useful.

Code:

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(N) {
    const swap = (i, j) =>
        [N[i],N[j]] = [N[j],N[i]]

    let len = N.length - 1, i
    for (i = len - 1; N[i] >= N[i+1];) i--
    let j = i + 1, k = len
    while (j < k) swap(j++,k--)
    if (i >= 0) {
        for (j = i + 1; N[i] >= N[j];) j++
        swap(i,j)
    }
};

OR

We loop through the numbers provided from end to start, looking for the first occurrence of a number decreasing, which will be our “left swap”. Next, we again look from right-to-left, until we find a number higher than our left swap, and swap the two numbers round. This effectively gives us the lowest possible “swap” that can be achieved for the given array.

To give a practical example, given the array [7, 2, 3, 1, 5, 4, 3, 2, 0] , we can see that the first decrease when looking right-to-left is from 5 to 1, making 1 our left swap. Going right-to-left again, we can then see that the first number higher than our left swap is 2, so we swap them around to give us [7, 2, 3, 2, 5, 4, 3, 1, 0].

Next, we sort the numbers to the right of the left-most swapped number to create the lowest possible permutation of the remaining digits. So in the example above, we take the numbers from the right of the moved-over 2, which are [5, 4, 3, 1, 0], and swap it for its lowest permutation (which we can achieve simply by ordering that array of numbers); [0, 1, 3, 4, 5]. By replacing the original values, this gives us the next greatest permutation of the original number: [7, 2, 3, 2, 0, 1, 3, 4, 5].

As another example, let’s take [3, 8, 3, 7, 5, 1]. So, going right-to-left, the first decrease comes at number 3 (index 2), and the first higher number than this, again going right-to-left, is 5, so we swap those around to give us [3, 8, 5, 7, 3, 1]. We then order the numbers on the right of the swapped-over 5 and end up with [3, 8, 5, 1, 3, 7], which is indeed the next lowest permutation.

In some cases, there may not actually be the next lowest permutation (for example in the array [3, 2, 1]). In these cases, in line with the question spec, we simply return the lowest permutation, which is easily obtained by ordering the entire array, which gives us [1, 2, 3].

Code:

var nextPermutation = function (nums) {
    if (nums.length <= 1) return;

    let leftHandSwap;

    // Loop through the provided numbers from right to left (excluding the first as we need something to compare it to)
    for (let i = nums.length - 2; i >= 0; i--) {
        // Check if this number is lower than the previous one (marks our left-hand swap)
        if (nums[i] < nums[i + 1]) {
            leftHandSwap = i;
            break;
        }
    }

    // Loop through the provided numbers from right to left
    for (let i = nums.length - 1; i > leftHandSwap; i--) {
        // If the number is bigger than the left-hand one
        if (nums[i] > nums[leftHandSwap]) {
            // Swap the numbers round
            [nums[i], nums[leftHandSwap]] = [nums[leftHandSwap], nums[i]];

            // Reverse the rest of the array
            let chopped = nums.splice(leftHandSwap + 1);
            chopped.sort((a, b) => a - b);
            nums.push(...chopped);
            return;
        }
    }

    // Right-hand swap not found, return lowest permutation instead
    nums.sort((a, b) => a - b);
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #31. Next Permutation

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!