Problem of the day: Queue with min operation | Everything Under The Sun
I came across this incredibly interesting problem that took me quite a while to solve: implementing a queue that supports the minimum operation, i.e., aside from the normal queue operations (enqueue, dequeue), it should also support a minimum operation, whereby a client could ask for the minimum element in the queue at any point. Before someone jumps in and says well that's just a min priority queue, no, there's a difference. Priority queues don't return elements in the order in which they were inserted but in the order of their priority. This queue has to return elements in the order in which they were inserted and also support querying for the current minimum element in the queue.
Now, I had to solve this problem for an online judge so I just had to return the right sequence of outputs for the given sequence of inputs i.e., I could read and preprocess the entire input before returning any output. This led me to go off in the wrong direction with this approach:
Read full article from Problem of the day: Queue with min operation | Everything Under The Sun
No comments:
Post a Comment