2 ms·
> With O(1) time, the easiest solution is just to store the minimum-to-date next to the value in the stack. Consulting the minimum is then just looking at the t
by Someone 5y ago
> With O(1) time, the easiest solution is just to store the minimum-to-date next to the value in the stack. Consulting the minimum is then just looking at the top value's minimum entry.
That won’t work. The all-time minimum may have been popped when the call to retrieve the lowest value currently on the stack is made.
As a first go, I would use a min-heap (https://en.wikipedia.org/wiki/Heap_(data_structure) https://en.wikipedia.org/wiki/Heap_(data_structure)) and a stack. Adding items then is a matter of adding them to both the heap and the stack. Popping would pop an item from the stack, look up any item in the heap with that value, and remove that. To get the minimum, look at the top of the min-heap.
Now, there probably is a way to combine these two data structures. I can’t rapidly think of one that’s more efficient in space and/or time, though.
(Edit: thinking more about it, I guess the problem also requires push and, in particular, pop to be O(1). Without that, the problem is trivial, as you can update the minimum value after every push or pop)
- jerf 5y agoThe original post may have some ambiguity in the term "minimum" but I read it as the minimum of the current contents of the stack, based on where the link the OP provided went to. When I said "minimum to date", I meant relative to the current contents of the stack in order. That is, if you push a value larger than the minimum on the top of the stack, you copy the minimum, if it's smaller, the pushed entry on the stack will be the pushed value, then the pushed value again as the minimum. This always keeps the minimum of the stack on the top of the stack. "All time minimum" would just be one place to store the minimum, since popping would do nothing to it. It is equivalent to the simplest algorithm to find the min of an unsort array/set/whatever.
- Someone 5y agoSorry, misinterpreted ”store the minimum-to-date next to the value in the stack”, reading it as if you had the stack and, next to it, a single “minimum to date” value.