Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Stack with min() operation

Sharing is caring!

Problem Statement
Create a stack data structure that supports the following operations as efficiently as possible:

Push, which adds a new element atop the stack,
Pop, which removes the top element of the stack,
Find-Min, which returns (but does not remove) the smallest element of the stack

Full Code

package stacksqueues;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import datastructures.MyStack;

/**
 * How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum
 * element? Push, pop and min should all operate in O(1) time.
 *
 * @author lucas
 */
public class E2 {
    protected static class MyStackWithMin extends MyStack {
        MyStack mins;

        public MyStackWithMin() {
            mins = new MyStack();
        }

        public void push(int item) {
            super.push(item);

            if (item <= min()) {
                mins.push(item);
            }

        }

        public Integer pop() {
            int item = (int) super.pop();
            if (item == min()) {
                mins.pop();
            }

            return item;
        }

        /**
         * Return min element on stack
         *
         * @return
         */
        public int min() {
            if (mins.isEmpty()) {
                return Integer.MAX_VALUE;
            } else {
                return (int)mins.peek();
            }
        }
    }

    public static void main(String[] args) {
        MyStackWithMin stack = new MyStackWithMin();

        stack.push(3);
        stack.push(31);
        stack.push(13);
        stack.push(2);
        stack.push(5);

        System.out.println(stack.min());
    }

}