JNEXT problem on SPOJ using stacks and queues

queue
spoj
stack

#1

The following link suggests us to solve JNEXT using stacks and queues:
https://www.codechef.com/certification/data-structures-and-algorithms/prepare#foundation

I tried it out however my algorithm is too inefficient and thus gives a TLE. Here is a link to my code:
https://www.codechef.com/viewsolution/22002636

How can we use stacks and queues to solve JNEXT efficiently?


#2

Your actual solution code is quite fast, albeit flawed. It’s your I/O code that is slowing you down. Here’s the same solution with faster I/O:

https://ideone.com/4YND67

One thing I’ve done is use a BufferedReader instead of a Scanner to read input. But the most important thing on this particular problem is to perform I/O a line at a time. Reading in a million character line is pretty fast, even with Scanner, and it is not difficult to get the digits out of it. Printing is also much faster if you create a char array that holds the answer and print that, instead of printing one character at a time.

The flaw I’ve noticed with your code is that it doesn’t print anything when no solution exists. Not -1, it prints nothing at all, not even a newline.


#3

what is the time complexity of above code ?