1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ Your problem is not 4 but 5. $\endgroup$ – babou Mar 29 '14 at 9:09
  • 1
    $\begingroup$ 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? $\endgroup$ – collapsar Mar 29 '14 at 9:09
  • $\begingroup$ 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. $\endgroup$ – collapsar Mar 29 '14 at 9:19
  • $\begingroup$ 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? $\endgroup$ – HaloKiller Mar 29 '14 at 9:36
  • $\begingroup$ @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 ? $\endgroup$ – collapsar Mar 29 '14 at 10:23
1
$\begingroup$

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)
  2. Delete Newest: O(1)
  3. Find Min: O(1)
  4. Update Min: O(1)

Additionally, your only requirement is to modify the list in order to keep a pointer to the newest element so that you could remove it in O(1).

Improve this answer
$\endgroup$
  • $\begingroup$ I forgot to say that I haven't yet learned about a Fibonacci data structure and I asked my lecturer and he said that I don't need a Fibonacci data structure here. $\endgroup$ – HaloKiller Mar 29 '14 at 8:57
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ I just need 1-4 to be O(1), and O(1) only. how do I do so? $\endgroup$ – HaloKiller Mar 29 '14 at 19:04
  • $\begingroup$ Oops. After considering it, in the solution I came up with, 2 isn't O(1) (in other variant, 3 isn't). $\endgroup$ – Alexey Romanov Mar 29 '14 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.