Wednesday, August 19, 2015

Leetcode: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.
Understand the problem:
The problem asks for implementing a stack, which support push, pop, top and getMin() in constant time. Note it requires all operations be in constant time. The operations like push, pop, and top are very easily to implement. 

The only issue is getMin(). We need to keep track of the minimum element that we have already pushed. One way is to use a priority queue. However, it would result in push and pop operations in O(logn) time since push and remove elements in pq requires O(logn) time. 

If we only keep track of the minimum number we have seen. What if the minimum number get poped? Then we will lose the minimum number. One solution is to use another stack, which only keeps track of the minimum number we have seen. When we push an element, we compare the pushed element with the top element of the minStack. If less, push the number into the minStack as well. When we pop an element, we need to check if the popped element is equal to the top element in the minStack. If yes, pop that as well. 

Code (Java):
class MinStack {
    private List<Integer> stack = new ArrayList<Integer>();
    private List<Integer> min = new ArrayList<Integer>();
    
    public void push(int x) {
        stack.add(x);
        if (min.isEmpty() || x <= min.get(min.size() - 1)) {
            min.add(x);
        }
    }

    public void pop() {
        int removed = stack.remove(stack.size() - 1);
        if (removed == min.get(min.size() - 1)) {
            min.remove(min.size() - 1);
        }
    }

    public int top() {
        return stack.get(stack.size() - 1);
    }

    public int getMin() {
        return min.get(min.size() - 1);
    }
}

1 comment:

  1. Why are you calling it stack and using a LinkedList? Is there some memory requirement reason? You could rather use Stack instead

    ReplyDelete