# “Minimum Stack”

I am now preparing for a test in my algorithms course and I have stumbled upon a question about a data structure which seems too trivial for me, but is probably not trivial at all.

The question is:

Let a "minimum stack" be a data structure that supports the following functions:

1. Creating a new empty data structure.

2. Inserting element X.

3. Returning the newest element and removing it from the data structure.

4. Returning the minimal element (the element with the smallest value). (without removing it)

5. Changing the minimal element's value to k. (Hint: say T is the number of elements added after the minimal element).

Now, I have thought about using a linked list which is isomorphic to an actual stack, hence elements can be added and removed only from the tail, but scanning the list from head to tail is possible.

I've checked and all the functions except 4 and 5 turn out to be O(1), but 4 turns out to be O(n) at best, and 5 turns out to be O(T).

My question is: How can I do 4 in O(1) time, so that all the other functions are also O(1)? I am not looking for full answers, just hints that will guide me to a full answer.

• Your problem is not 4 but 5. – babou Mar 29 '14 at 9:09
• Hint: think of how the Information about the minimal Element in the Stack changes with ordinary Stack operations. Which data structure accomodates for these Kinds of changes? – collapsar Mar 29 '14 at 9:09
• BTW i don't think that you will manage 5. in $O(1)$ because if you did you could sort in $O(n)$ by applying the step $n$ Times for strictly decreasing $k$ after Inserting $n$ (Unordered) elements starting with the empty Minimum Stack. – collapsar Mar 29 '14 at 9:19
• I don't understand your hint about the information. What do you mean? The index of the minimal element or the value of it? or maybe something else? – HaloKiller Mar 29 '14 at 9:36
• @Trinarics take a 'change' to be a change to the pair of position and/or value of the minimal element. thus you can answer yourself: which operations will cause what kind of change ? does the occurrence of a change on a given operation depend on the actual data in your data structure ? in which way ? – collapsar Mar 29 '14 at 10:23

The trivial approach would suggest a Fibonacci based data structure, but I presume that removing the newest element would be non-ideal. Therefore maybe a sorted-list would be better. The complexities would be:

1. Insertion: O(n)
I don't think it's possible for all 5 to be $O(1)$. Consider sequence of operations 5 (setting the new value to be very large) -- 4 -- 5 (setting the new value to be very large) -- 4 -- etc. It will return all elements of the stack in sorted order in $O(n)$, and so it must effectively be stored in sorted order already. But then 5 can't find the proper place to insert the new value in $O(1)$! OTOH, if you just need 1-4 to be $O(1)$ (based on your question), you can just add a single piece of extra data to the linked list.
• Oops. After considering it, in the solution I came up with, 2 isn't O(1) (in other variant, 3 isn't). – Alexey Romanov Mar 29 '14 at 20:16