@Divye:
Awesome solution dude with amortized complexity of O(1)!
The examples made things even clearer :)
On Jun 26, 8:13 am, DK divyekap...@gmail.com wrote:
I've solved it for find_min() - the find_max implementations are analogous.
Example:
i = insert
d = delete
i 1 -
q - 1
dq - 1 --
@DK - your solution works great but my only concern is that for the
worst case, insert() is not really O(1). For example, if you have 1000
elements being inserted in ascending order and then 1001'st element is
smaller than the first element, the insert() will become O(n).
On Jun 25, 10:13 pm, DK
you can use an auxiliary stack to store the minimum values.Lets call
it minstack.
Whenever you push an Element in the Original stack, compare it with
the top of minstack.
if it is lesser than top of minstack then push this one on both the
stacks and if not then
push the top of minstack again on
@Ross: I was thinking about this same question 6 months ago. I never posted
thoughts anywhere, but here's my solution using 1 Queue and 1 Double Ended
Queue. You would never have seen this solution before on the internet.
Hence, I claim authorship. :D
Also, somebody posted this question on
@piyush,
Dude, how will that make findmin() to be O(1) because, once the
minimum element is
deleted, u would require changes in the others .. Correct me if i am
wrong..
Eg:
consider inserting, 1 5 6 7 9 in order into the circular LL.
When u make each node keep track of the minm before it, all will
ohh sorry, my bad..I missed that issue...then we can use the same logic
of using one more stack that we use for implementing modified stack keeping
track of the min()..I hope this will solve the issue
On Fri, Jun 24, 2011 at 3:57 PM, ross jagadish1...@gmail.com wrote:
@piyush,
Dude, how
@Piyush:
Dude, that method u suggested wont work ...
It works for stacks because, while deletion of an element, We may
verify if it is in the top of second stack and delete it..
(Since both the data structures are LIFO)
Here in this case, if u delete, you cannot remove the top of stack and
delete
