Wednesday, October 11, 2017

[Problem2 SPOJ-JNEXT] Next Lexicographical Permutation Algorithm; Ad-Hoc


I was solving SPOJ-JNEXT, and from the comments section I came across this page:

Nice explanation but there's a caveats to keep in mind to understand the working better-

It mentions:
If there is no such element – i.e. the entire sequence is non-decreasing – then this is already the last permutation.
It should rather be "non-increasing" instead of "non-decreasing".

My approach to solving this problem was similar so I won't bore you with another copy of how the algorithm works here: you may use the explanation in link above (with the correction in mind).

Tested and accepted:,chandniverma/

Time Complexity of get_next_perm() in worst case: O(n) where n is the number of digits in each test case in the input.
Space required: O(n)