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)

Tuesday, October 10, 2017

[Problem1 SPOJ:STPAR] Stacks use case; Ad-hoc

Starting last weekend I have started picking up problems from the certification syllabus of the Codechef Certified Data Structure & Algorithms Programme: CCDSAP ( ). I would definitely recommend solving the practice material even if you are not willing to go for the certification.

I'll solve these in increasing order of difficulty and not necessarily sequentially while skipping the cake-walk ones and also probably the ones that I have done previously.
This way I can ensure this series of self-paced hackathon-cum-blogathon will eventually come to an end, with an end to the problems in this syllabus.


I had done this problem earlier so it was a good candidate for an ice-breaker. I first (sometime in 2010) solved this in Java. This time in C++ using an on-the-fly algorithm that doesn't store all inputs before processing them but processes each input as it comes in a single pass.

Tested and accepted at :,chandniverma/

The time complexity is O(n).
Space needed is O(n) (actually only n).

Friday, October 6, 2017

Blogging after a long time... turning my blog into an algorithmist's blog solving this world's time and memory efficiency problems in computing.

... Since I cannot talk much about what things I work on as part of my day job and since I feel that's making my blog boring and making the viewers wait a lot between my blogging sessions, I've decided to start blogging about algorithmic programming skills which every computer software engineer should be good at!

I'll do this because I like spending my free time in sharpening my algorithmic skills and while I take notes, why not should someone-on-the-web learn something out of it?

I'll post codes into a Github public repository which will have C++ solutions (why C++? due to it's speed, presence of STL and intuitiveness of Object Orient-ism) tested by online judges and if I learn something triggering an Aha moment, I'll jot down a quick blog post with links to an actual runnable code and the problem it solves.

You all can send thank you notes and suggestions for improvements my way, as always!

Sounds fun?
Watch this space!