Stack question

Status
Not open for further replies.

electroRF

Member
I ran into the following question.
You got a stack, and you need to design the push and pop functions so you could always know that min value in the stack.
Push, Pop, and Min should all be with time complexity O(1).

The solution was lovely, when pushing an item to the stack which is lesser than the current min, you enter (2xitem - min), i.e. item+item-min, and update item to be the new min.
That way, this value is smaller than the new min, and when you pop it off, you'll know to return the new min and you'd also know how to retrieve the previous min.

My question is, why did they decided on 2xitem - min?

Why not for example: item-1? what is special with 2xitem - min?

Thank you.
 
Can you post the full algorithm? Does the algorithm save the current "min" in a variable?

I think the reason is that "2*item - min" contains enough information to solve for both next "min" and "item" to pop.. and can also handle dublicate "min" values. I need to know the algorithm details to be more specific.
 
Last edited:
Status
Not open for further replies.
Cookies are required to use this site. You must accept them to continue using the site. Learn more…