# "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. Mar 29, 2014 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? Mar 29, 2014 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. Mar 29, 2014 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? Mar 29, 2014 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 ? Mar 29, 2014 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). Mar 29, 2014 at 20:16