Min Stack

July 27, 2012

Today’s exercise continues our occasional series of exercises based on interview questions:

Design a data structure that provides push and pop operations, like a stack, plus a third operation that finds the minimum element. All three operations must perform in constant time. You may assume that all elements are distinct.

Your task is to write the three indicated functions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

14 Responses to “Min Stack”

  1. [...] today’s Programming Praxis exercise, our goal is to create s stack-like data structure that can push, pop [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/27/programming-praxis-min-stack/ for a version with comments):

    empty :: ([a], [a1])
    empty = ([], [])
    
    push :: Ord a => a -> ([a], [a]) -> ([a], [a])
    push x (ms,xs) = (if null ms || x < head ms then x:ms else ms, x: xs)
    
    pop :: Eq a => ([a], [a]) -> (Maybe a, ([a], [a]))
    pop (m:ms,x:xs) = (Just x, (if m == x then ms else m:ms, xs))
    pop s           = (Nothing, s)
    
    min' :: ([a], [a]) -> Maybe a
    min' (m:_, _) = Just m
    min' _        = Nothing
    
  3. Javascript. I used a function constructor.

    
    function MinStack() {
    	var pushPopStack= []
    		, minimumsStack = []
    		, n = 0 //Num of elems in structure
    		, m = 0;// num of elems in min stack
    
    
    	this.push = function (elem) {
    
    		//If num of elems is zero, push to both stacks. 1st elem
    		//is also a minimum
    		if (n === 0) {
    			minimumsStack.push(elem);
    			m++;
    		}
    		//If new elem is lower than current min, we push a new min
    		else if (elem < minimumsStack[m-1]) {
    			minimumsStack.push(elem);
    			m++;
    		}
    
    		pushPopStack.push(elem);
    		n++;
    
    	};
    
    	
    	this.pop = function () {
    
    		if (n === 0) {
    			throw "No elems";
    		}
    
    		var elem = pushPopStack.pop();
    		n--;
    
    		//If elem matches pop of min stack, pop that one
    		//off too
    		if (elem === minimumsStack[m-1]) {
    			m--;
    			minimumsStack.pop();
    		}
    		return elem;
    	};
    
    	//Return minimun
    	this.min = function () {
    		return minimumsStack[m-1];
    	};
    
    	this.toString = function () {
    		var str = pushPopStack + " | " + minimumsStack;
    		return str;
    	};
    }
    
    var ms = new MinStack();
    
    
  4. Mike said

    Python version:

    class MinStack:
    	def __init__(self):
    		self.mins = []
    		self.stack = []
    
    	def push(self, item):
    		self.stack.append(item)
    		if not self.mins or item <= self.mins[-1]:
    			self.mins.append(item)
    
    	def pop(self):
    		item = self.stack.pop()
    		if item == self.mins[-1]:
    			self.mins.pop()
    		return item
    
    	def min(self):
    		return self.mins[-1]
    

    For the push operation, I think you need to add the new item to the min stack if it is returns 0, but also clears a 0 from the minimum stack
    minimum –> should still be zero

  5. Mike said

    Sorry, a less than symbol messed up my comment.

    I think the push operation needs to add the new item to the minimum stack when it is less than or equal to the current minimum. Otherwise, a minimum item could get popped off to soon. Consider this sequence of operations:

    push 5
    push 3
    push 3
    pop          <- returns 3, but also removes 3 from the top of the min stack
    minimum  <- should still return 3
    
  6. programmingpraxis said

    The problem text states that all items are distinct.

  7. madscifi said

    Mike, pushing 3 onto the stack twice is actually not legal according the specification: “You may assume that all elements are distinct”.

  8. kawas said

    Clojure solution almost similar to the Haskell one

    (defn empty' [] (vector '() '()))
    
    (defn min' [[_ mins]] (first mins))
    (defn peek' [[stack _]] (first stack))
    
    (defn push' [[stack mins] x]
      (vector (conj stack x)
              (if (and (seq mins) (> x (first mins))) mins
                (conj mins x))))
    
    (defn pop' [[stack mins]]
      (vector (rest stack)
              (if (not= (first stack) (first mins)) mins
                (rest mins))))
    

    Alternate solution, using protocol and an helper constructor

    (defprotocol IMinStack
      (min' [this])
      (peek' [this])
      (push' [this e])
      (pop' [this]))
    
    (defrecord MinStack [_stack _mins]
      IMinStack
        (min' [this] (first _mins))
        (peek' [this] (first _stack))
    
        (push' [this e]
          (MinStack.
            (conj _stack e)
            (if (and (seq _mins) (> e (first _mins))) _mins
                (conj _mins e))))
    
        (pop' [this]
          (MinStack.
              (rest _stack)
              (if (not= (first _stack) (first _mins)) _mins
                  (rest _mins)))))
    
    (defn empty' [] (MinStack. '() '()))
    

    Whatever the solution you can use it the same way

    (empty')
    (min' (empty'))
    (peek' (empty'))
    (pop' (empty'))
    (push' (empty') 5)
    (push' (push' (empty') 5) 3)
    (peek' (push' (push' (empty') 5) 3))
    (push' (push' (empty') 5) 7)
    (peek' (push' (push' (empty') 5) 7))
    (pop' (push' (push' (empty') 5) 3))
    (pop' (push' (push' (empty') 5) 7))
    (peek' (pop' (push' (push' (empty') 5) 7)))
    
  9. A Go solution similar to the Python one:

    
    package main
    
    import "fmt"
    
    type MinStack struct {
    	stack []int
    	mins  []int
    }
    
    func NewMinStack() *MinStack {
    	return &MinStack{make([]int, 0), make([]int, 0)}
    }
    
    func (st *MinStack) String() string {
    	if st.Empty() {
    		return "empty stack"
    	}
    	return fmt.Sprintf("top=%d min=%d", st.Top(), st.Min())
    }
    
    func (st *MinStack) Empty() bool {
    	return len(st.stack) == 0
    }
    
    func (st *MinStack) Push(n int) {
    	st.stack = append(st.stack, n)
    	if len(st.mins) == 0 || n <= st.mins[len(st.mins)-1] {
    		st.mins = append(st.mins, n)
    	}
    }
    
    func (st *MinStack) Top() int {
    	if st.Empty() {
    		panic("empty stack")
    	}
    	return st.stack[len(st.stack)-1]
    }
    
    func (st *MinStack) Pop() int {
    	if st.Empty() {
    		panic("empty stack")
    	}
    	n := st.stack[len(st.stack)-1]
    	st.stack = st.stack[0 : len(st.stack)-1]
    	if n == st.mins[len(st.mins)-1] {
    		st.mins = st.mins[0 : len(st.mins)-1]
    	}
    	return n
    }
    
    func (st *MinStack) Min() int {
    	if st.Empty() {
    		panic("empty stack")
    	}
    	return st.mins[len(st.mins)-1]
    }
    
    func main() {
    	st := NewMinStack()
    	st.Push(3)
    	st.Push(4)
    	st.Push(5)
    	fmt.Println(st)
    	st.Push(1)
    	st.Push(2)
    	fmt.Println(st)
    	st.Pop()
    	st.Pop()
    	fmt.Println(st)
    }
    
    
  10. Ted said

    Learning a bit of c++:

    #ifndef CSTACK_H
    #define CSTACK_H
    using namespace std;

    struct node {
    int x;
    node *next;
    };

    class CStack {
    public:
    CStack();
    CStack(const CStack& orig);
    virtual ~CStack();
    void push(int x);
    int pop();
    int minimum();

    private:
    int min;
    node *head;
    };

    #endif /* CSTACK_H */

    #include “CStack.h”
    #include
    #include
    using namespace std;

    CStack::CStack() {
    min=1000;
    }

    CStack::CStack(const CStack& orig) {
    }

    CStack::~CStack() {
    }

    int CStack::minimum() {
    return min;
    }
    void CStack::push(int x) {
    node *current;
    if(head != NULL){
    current = new node;
    current->x=x;
    if(min>x){
    min=x;
    }
    current->next=head;
    head=current;
    }
    else{
    head = new node;
    min=x;
    head->x=x;
    }
    }

    int CStack::pop() {
    int ret = head->x;
    head=head->next;
    return ret;
    }

  11. swuecho said

    Perl6 version:

    class Min_stack {
    
        has @.stack;    
        has @.min;
        
    
        method push($item) {
    	push @.stack, $item;  
    	if @.min==0 or @.min[*-1] > $item {
    	    push @.min, $item;
    	}
        }
    
        method pop() {	
    	my $item=pop @.stack;
    	if $item == @.min[*-1] {
    	    pop @.min;
    	}
    	return $item;
        }
    
        method min() {
    	@.min[*-1];
        }
    
    }
    
  12. [...] problem: Min Stack Design a data structure that provides push and pop operations, like a stack, plus a third operation [...]

  13. swuecho said

    should rename the method name as http://swuecho.wordpress.com/2012/08/04/min-stack/, because of names conflict.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 599 other followers

%d bloggers like this: