Design MinMax Queue

JavaView on GFG

Intuition

Queue supporting O(1) min and max queries. Use two deques (one for min, one for max) alongside main queue.

Algorithm

1Enqueue x: pop from back of minDeque while back > x; pop from back of maxDeque while back < x. Push to both.
2Dequeue: if front of minDeque == front of queue: pop minDeque. Same for maxDeque. Pop main queue.

Common Pitfalls

•Monotonic deques maintain min and max. Front of each deque is current min/max. O(1) amortized per operation.

Design MinMax Queue.java

Java

// Approach: Use two deques (monotonic) tracking min and max alongside the main queue.
// On dequeue, remove from front of monotonic deques if they match.
// Time: O(1) amortized Space: O(n)
import java.util.*;

class SpecialQueue {

    class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    class Entry {
        Node node;
        int val;

        Entry(Node node, int val) {
            this.node = node;
            this.val = val;
        }
    }

    Node front, rear;
    HashSet<Node> active;
    PriorityQueue<Entry> maxHeap, minHeap;

    public SpecialQueue() {
        rear = new Node(-1);
        front = rear;
        active = new HashSet<>();
        maxHeap = new PriorityQueue<>((a, b) -> b.val - a.val);
        minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    }

    public void enqueue(int val) {
        Node node = new Node(val);
        rear.next = node;
        rear = node;
        active.add(node);
        maxHeap.add(new Entry(node, val));
        minHeap.add(new Entry(node, val));
    }

    public void dequeue() {
        active.remove(front.next);
        front = front.next;
    }

    public int getFront() {
        return front.next.val;
    }

    public int getMin() {
        cleanMin();
        return minHeap.peek().val;
    }

    public int getMax() {
        cleanMax();
        return maxHeap.peek().val;
    }

    private void cleanMin() {
        while (!minHeap.isEmpty() && !active.contains(minHeap.peek().node))
            minHeap.poll();
    }

    private void cleanMax() {
        while (!maxHeap.isEmpty() && !active.contains(maxHeap.peek().node))
            maxHeap.poll();
    }
}

Was this solution helpful?