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.

Example 1:

Input ["MinStack","push","push","push","getMin","pop","top","getMin"] 
[[],[-2],[0],[-3],[],[],[],[]] 

Output [null,null,null,null,-3,null,0,-2] 

Explanation 
MinStack minStack = new MinStack(); 
minStack.push(-2); 
minStack.push(0); 
minStack.push(-3); 
minStack.getMin(); // return -3 
minStack.pop(); 
minStack.top();    // return 0 
minStack.getMin(); // return -2

Constraints:

  • Methods poptop and getMin operations will always be called on non-empty stacks.

​To make a constant time getMin(), we need to keep track of the latest minimum value for each element in the stack. We can solve the problem by defining the stack using a LinkedList. Following is the Node for the LinkedList.

class Node {
  int value;
  int min;
}

An instance of Node is the entry of the Stack, where :

  • value: Value of the Node or Stack element.
  • min: Minimum value until this node is pushed into the Stack.

Following is the Implementation:

Note : java.util.LinkedList is Doubly-linked list implementation of the List and Deque interfaces.

import java.util.*;

class Node {
    int value;
    int min;

    public Node(int v, int m) {
        value = v;
        min = m;
    }
}

class MinStack {

    private LinkedList<Node> data;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        data = new LinkedList<>();
    }

    public void push(int x) {
        Node node = null;
        if (data.isEmpty()) {
            node = new Node(x, x);
        } else {
            Node prev = data.getLast();
            node = new Node(x, Math.min(x, prev.min));
        }
        data.add(node);
    }

    public void pop() {
        if (!data.isEmpty()) data.removeLast();
    }

    public int top() {
        return data.isEmpty() ? -1 : data.getLast().value;

    }

    public int getMin() {
        return data.isEmpty() ? -1 : data.getLast().min;
    }
}

Categories: Stack

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s