Solution: Next Permutation

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #31 (Medium): Next Permutation

---

Description:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

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]

Example 4:
Input:	nums = [1]
Output:	[1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

---

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

---

Javascript Code:

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)
    }
};