LeetCode problem #31 — Next Permutation (JavaScript)

In this LeetCode problem, we’re asked to write a function that, when provided an array of numbers, returns the next lexicographically greater permutation of those numbers. I would most definitely group this problem into the “why on earth is this a thing?” pile, but as the comments indicate it has come up in interviews, I’ll go ahead and run through it.

First off, what on earth does “next lexicographically greater permutation” mean? Basically, it means the next biggest number that you can achieve by rearranging the given numbers. So in other words, the next lexicographically greater permutation of [1, 2, 3] is [1, 3, 2] , because the other permutations ([2, 1, 3] , [2, 3, 1] , [3, 2, 1] and [3, 1, 2]), are all higher than [1, 3, 2] , and are thus not the next one.

To give another example, the potential permutations of [4, 8, 6] are [4, 6, 8] , [6, 8, 4], [6, 4, 8], [8, 6, 4] and [8, 4, 6], which means the next largest one to the original would be [6, 4, 8].

Of course, sometimes there will be no greater permutation, and so in that case you are instructed to return the lowest permutation available, which in the previous example would be [4, 6, 8].

Solution #1: Reverse-loop

LeetCode user ybmlk posted a wonderfully elegant solution, in which 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 round 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 achieved 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 a 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].

All of the above might sound a little daunting, but it’s actually pretty close to how we approach the problem as a human. Say for example you’re given the number [8, 1, 3, 0, 4] and asked to find the next highest permutation. You would naturally look for the first pair of numbers on the right that you can swap to make a higher number, which in this case is 0 and 4. If the set of numbers is a little more complex, such as the earlier case of [3, 8, 3, 7, 5, 1], the initial process remains the same; we still look for the first 2 “swappable” numbers, but we also have to sort the numbers after the swap, as outlined earlier.