Very concise Java solution with Deque interface

  • 12

    The solution is pretty straightforward, keep a minStack besides the underlying stack. During push: push a new item if it's smaller or equals than the current minimum. During pop: if the current item to be popped equals to the top of minStack then pop that one aswell.

    Deque<Integer> stack = new LinkedList<>();
    Deque<Integer> minStack = new LinkedList<>();
    public void push(int x) {
        if(minStack.isEmpty() || minStack.peek() >= x) {
    public void pop() {
        int x = stack.pop();
        if(x == minStack.peek()) {
    public int top() {
        return stack.peek();
    public int getMin() {
        return minStack.peek();

  • 0

    Why Deque, you seems to be needing just Queue, am I wrong? I mean the code here is not utilizing the capabilities of Deque and could be done via Queue only?

  • 0

    Actually, you need a LIFO, not a FIFO, and in Java, to use a Stack you should use the Deque interface (the "original" Stack interface is kinda deprecated, see:

  • 0

    This is my solution using Deque:

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<List<Integer>> result = new ArrayList<>();
        Deque<TreeNode> dq = new ArrayDeque<>();
        boolean ltr = true;
        while (!dq.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int i = dq.size(); i > 0; i--) {
                TreeNode node;
                if (ltr) {
                    node = dq.removeFirst();
                    if (node.left != null) dq.addLast(node.left);
                    if (node.right != null) dq.addLast(node.right);
                } else {
                    node = dq.removeLast();
                    if (node.right != null) dq.addFirst(node.right);
                    if (node.left != null) dq.addFirst(node.left);
            ltr = !ltr;
        return result;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.