fbpx
Home / LeetCode / 155. Min Stack | Leetcode Solutions | Master Problem Solving

155. Min Stack | Leetcode Solutions | Master Problem Solving

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.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Solution

The Idea here is to use Two Stack Data Structure one for keep adding the items in main stack and the other one to keep track the min value for items so every time we push item in minTrackStack we get the minimum value in stack and compare it with the inserted item and that’s it.

class MinStack {

    Stack<Integer> mainStack;
    Stack<Integer>minTrackStack;
    /** initialize your data structure here. */
    public MinStack() {
        mainStack = new Stack<>();
        minTrackStack = new Stack<>();
    }
    
    public void push(int x) {
        mainStack.push(x);
        if(minTrackStack.isEmpty())
            minTrackStack.push(x);
        else
            minTrackStack.push(Math.min(minTrackStack.peek(),x));
    }
    
    public void pop() {
        mainStack.pop();
        minTrackStack.pop();
    }
    
    public int top() {
        return mainStack.peek();
    }
    
    public int getMin() {
        return minTrackStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

About admin

Leave a Reply

Your email address will not be published. Required fields are marked *