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” after 1,2,3 out of the alternative options listed above.

An algorithm exists (from Wikipedia)

  • Find the largest index k such that a[k] < a[k + 1]. If there is no such index, the permutation given is the last permutation (and the LeetCode problem requests we return the array sorted). We find the index out of place to stop this being the last permutation.
  • Find the largest index i greater than k such that a[k] < a[i]. Find the element in the right-hand side of the array

The Narayana Panditha’s algorithm — diagrammatically

The code — in Swift

Want to get in contact? Get in touch on Twitter:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store