LeetCode 31 Next Permutation: Narayana Pandita’s algorithm

Swift interview practice

Leetcode Problem 31. Next Permutation asks us to rearrange a list of numbers into the lexicographically next permutation of that list of numbers.

The naive solution

Usually the naive solution is reasonably easy, but in this case this is not true. To try to get a list of all the permutations of Integers.

One solution to this is to take any number as the first number and append it to the permutations of any other numbers, which would give us a list of permutations. Order them, and pick out the next available permutation which requires us to sort the list of permutations.

The naive code — in Swift

Note: The code for this is actually just as tricky as for the more efficient solution. This code also runs too long for LeetCode’s rather tight time constraints on this problem.

The Narayana Panditha’s algorithm — pseudocode

For example

1,2,3 when rearranged can be in alternative orders (3,2,1; 3,1,2; 2,1,3; 2,3,1; 1,3,2) and out of these 1,3,2 is the “next”…