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 caveat 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".

[UPDATE: It has been corrected on the website The author personally wrote a thank you note to me confirming  the error and rectifying it.]

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 complexity: O(n)

No comments:

Post a Comment