'Amazon interview: Min stack

I recently had my Amazon interview for SDE. I was asked to design a stack which does push, pop and min in O(1).
I got the logic and implemented the push of the stack. While implementing push of the new stack, I called push on given stack and min stack which were a part of new stack. The interviewer told me that i couldn't do it like that as push would be a recursive call. I explained to him, that we could name it differently, but he insisted that both operations on old stack and new stack be called push.

How could I achieve the same?

algorithmdata-structuresstack


Solution 1:[1]

One way to implement this is to keep track of the minimum of all values that are below some element in the stack.
For every element in the stack you will actually have 2 elements. One with the actual value, and above it, the minimum value of all the elements underneath it.

  1. Push - Compare the new value with the top minimum and push both the value and the current minimum.
  2. Pop - Just pop twice from the stack (both the value and the current minimum).
  3. Min - Return the top of the stack.

Example: For elements 7, 9, 3, 5, 1, 2 (in this order) the stack will be:

TOP:    1 <--- min(7,9,3,5,1,2)
        2
        1 <--- min(7,9,3,5,1)
        1
        3 <--- min(7,9,3,5)
        5
        3 <--- min(7,9,3)
        3
        7 <--- min(7,9)
        9
        7 <--- min(7)
        7

Solution 2:[2]

The solution is simple and elegant — Use an extra stack to maintain the minimums. 

1.To retrieve the current minimum, just return the top element from minimum stack.
2.Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack
too.
3.When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum
stack too.

Solution 3:[3]

Make each value in a regular stack a vector with 2 elements, where the first element would represent a value and a second one a running minimum.

Wrapping methods could mask a vector, so only a regular value would be available in the interfaces and signatures.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 ARVINDER SINGH
Solution 3 Axalix

Related Questions