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.
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.