JNEXT problem on SPOJ using stacks and queues

The following link suggests us to solve JNEXT using stacks and queues:

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?

1 Like

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.

what is the time complexity of above code ?

i solved this problem using stacks and vectors. but i am getting run time error(actually SIGSEGV)

https://ideone.com/vZcyqN.

but i don’t know why it is happening at all. even when my code is running in vscode editor just fine with the sample inputs given in the question. the code is in c++ and i am using gcc 8.3

My soln using python https://ideone.com/QzGLSS [ Stack and queue ]
Using C++ : https://ideone.com/sKRdr0 [ Did nothing. Just used next_permutation ]

Your solution TLE most probably beacuse you are youing Java. Which has very slow I/O.

1 Like

And… If you don’t mind which level of exam you are appearing?

Actually I wouldn’t just call it Stack/Queue. The problem is actually solved by a category of Stacks/Queues called as Monotonic Stacks/Queues. Now, there is nothing special about Monotonic Stacks/Queues, they are just ordinary Stacks/Queues with the property that the elements in them are in a monotonic sequence. That is either increasing or decreasing. You may have encountered them before but their uses is so common that you may have not even realised. Anyway, here is a good resource to learn about Monoque(as they are often called)- Monotonic Queue Summary
Coming back to the question, Monoque has a very little role in the solution, in-fact you would be fine without using them at all. They only come in one of the last steps of the problem. Actually at that stage you have some digit d at some index i in the string and you want to find a digit d’ to the right of index i(say i’) such that d’ > d and i’ is maximum possible. In other words, you want to find the digit farthest to the right from d which is greater than it. Now, it so happens that solution of the question creates a situation such that every digit in the range of index [i+1, string.length - 1] is sorted. So, suppose you are scanning digits from right to left and pushing every digit in a Stack untill you reach index i(or digit d) then to find d’ - You can simply keep popping all digits from the stack until you find a digit < d(say d’’) then our required digit(d’) will be the digit just popped previously. This follows from the property of a Monotonic Stack.
Of-course, the thing is so simple that you don’t need a Stack at all. But Monotonic Stacks are quite useful in a variety of situations such as in questions like ‘Largest Rectangular Area in a Histogram’ or ‘Find the amount of water trapped in Histograms’, or ‘Smallest window containing sum >= K’.

5 Likes

https://ideone.com/5dq3oI ( Python 3)

Why my solution giving TLE? help!

the TC of next_permutations is high is it worth it ??

first of all your solution is wrong
use these test cases, input -
5
5
1 5 4 8 3
5
1 5 3 8 4
5
1 3 5 8 4
6
5 3 4 9 7 6
10
1 4 7 4 5 8 4 1 2 6
expected output is -
15834
15438
13845
536479
1474584162
your output -
15834
15843
13845
539764
1474584162

can you please share your solution.
i learned monotone stack but idk how i am using it in wrong way.

please can you help me for same problem …why it is giving wrong ans? code link–> PZJxC4 - Online C++ Compiler & Debugging Tool - Ideone.com