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