# 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:**