An Efficient MinMaxQueue

The problem is to design a queue such that methods to find the current maximum or minimum integer in the queue are efficient in terms of their running time complexity, while having a maximum of O(logn) insertion and removal from the queue.

Now if we were to change the question to a MinMaxStack, we can actually implement the getMax() and getMin() methods in constant time O(1). It's done by using multiple stacks (one for the original, the max values, the min values) and we just have to change our push and pop methods so that they will add the values to the max stack, or the min stack, accordingly. It's a little trickier with queues because they are First-In-First-Out (FIFO) data structures. . It is possible to get the min and the max in constant time by simulating a queue with a MinMaxStack, but then we will have an amortized O(1) for the removal method.

We can still do very efficient getMax() and getMin() with queues though. I have not seen a way to do all operations in constant time, and I'm not sure if it's possible or not, but we can compute the min and max in logarithmic time O(logn) by taking advantage of binary-search-trees (BST).

BSTs can be utilized here because you can get the min or the max of the tree in O(logn), and that's because of the way nodes are structured in BSTs (the left child is less than the root, and the right child is always less than or equal to the root).

With this structure it wouldn't be hard to implement a queue with getMax() and getMin(), both of which have a O(logn) running time.

Let's go through how we implment a BST. The following code is just BST that supports integer nodes, but your own implementation of a BST would also work.

class BST {

    private class Node {
        int val;
        Node left, right, link;

        public Node(int v) {
            this.val = v;
            this.left = this.right = this.link = null;
        }
    }

    Node root;

    public BST(){
        this.root = null;
    }

    public Node insert(int key) {
        if(this.root == null){
            this.root = new Node(key);
            return this.root;
        }
        return insert(this.root, key);
    }

    private Node insert(Node x, int v) {
        if (x == null) {
            return new Node(v);
        }

        if (v >= x.val)
            x.right = insert(x.right, v);
        else
            x.left = insert(x.left, v);


        return x;
    }

    public void remove(int v){
        this.root = remove(this.root, v);
    }

    public Node remove(Node root, int v){
        if (root == null)
            return null;

        if (v < root.val)
            root.left = remove(root.left, v);
        else if (v > root.val)
            root.right = remove(root.right, v);
        else if (root.left != null && root.right != null){
            root.val = getMin(root.left).val;
            root.right = remove(root.right, root.val);
        }else
            root = root.left != null ? root.left : root.right;

        return root;
    }

    public int getMin(){
        if(this.root == null) return Integer.MAX_VALUE;
        return getMin(this.root).val;
    }

    public Node getMin(Node root){
        if (root == null)
            return null;

        Node current = root;
        while(current.left != null){
            current = current.left;


        return current;

    }

    public int getMax(){
        if(this.root == null) return Integer.MIN_VALUE;
        return getMax(this.root).val;
    }

    public Node getMax(Node root){
        if (root == null)
            return null;

        Node current = root;
        while(current.right != null){
            current = current.right;
        }

        return current;
    }
}

A pretty simple and straightforward implementation of a BST.  The idea of the MinMaxQueue is also very simple. We will create a normal queue, that we will be using to add our elements in, and BST that we also insert our elements in. Whenever we run getMax() or getMin(), we just call our methods getMax() or getMin(), respectively, from the BST object. The BST will return the value in O(Logn). If we poll (remove) an element from the queue, we also remove the same value from the BST as well. The insertion and removal of items from the queue is constant time, but O(Logn) in the BST. 

public class MinMaxQueue {

    private Queue <Integer> q;
    private BST values;

    public MinMaxQueue(){
        this.q = new LinkedList<>();
        this.values = new BST();
    }

    public boolean add(int k){
        values.insert(k);
        q.add(k);
        return true;
    }

    public boolean poll(){
        if(q.isEmpty()) return false;
        int removed = q.poll();
        values.remove(removed);
        return true;
    }

    public int getMax(){
        if(q.isEmpty()) return Integer.MIN_VALUE;
        return values.getMax();
    }

    public int getMin(){
        if(q.isEmpty()) return Integer.MAX_VALUE;
        return values.getMin();
    }

    public static void main(String[] args){
        MinMaxQueue mq = new MinMaxQueue();

        mq.add(400);
        mq.add(300);
        mq.add(200);
        mq.add(100);

        System.out.println(mq.getMax()); // 400
        mq.poll();
        System.out.println(mq.getMax()); // 300
        mq.poll();
        System.out.println(mq.getMax()); // 200
        mq.poll();
        System.out.println(mq.getMax()); // 100
        mq.poll();
        System.out.println(mq.getMax()); // -2147483648 because it's empty
    }

}

Take a few minutes to read the code. 

Thanks for reading! and let me know if you have any feedback.