Deque and Priority Queue (Sliding Window Max · Top K)

Sliding Window Maximum (LeetCode 239)

Using a monotonic decreasing double-ended queue (Deque): The front of the queue always holds the index of the maximum value within the current window.

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();  // Stores indices, maintain decreasing order

    for (int i = 0; i < n; i++) {
        // 1. Remove indices that are out of the current window range
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // 2. Maintain monotonic decrease: remove indices of values smaller than current
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        
        // 3. Record the maximum (head of deque) once window size reaches k
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

Top K Frequent Elements (Heap Approach)

int[] topKFrequent(int[] nums, int k) {
    // 1. Frequency count
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int n : nums) freqMap.merge(n, 1, Integer::sum);

    // 2. Min-Heap (retains the top k most frequent elements)
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    for (Map.Entry<Integer, Integer> e : freqMap.entrySet()) {
        minHeap.offer(new int[]{e.getKey(), e.getValue()});
        // Keep heap size at k; the least frequent element is polled
        if (minHeap.size() > k) minHeap.poll(); 
    }

    // 3. Extract and return in descending order
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = minHeap.poll()[0];
    return result;
}

Kth Largest Element in a Stream (LeetCode 703)

class KthLargest {
    private final PriorityQueue<Integer> minHeap;
    private final int k;

    KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<>(k); // Maintain a min-heap of size k
        for (int n : nums) add(n);
    }

    public int add(int val) {
        minHeap.offer(val);
        // Evict smallest to keep only the k largest elements
        if (minHeap.size() > k) minHeap.poll();
        // The root is the k-th largest overall
        return minHeap.peek(); 
    }
}

Merge K Sorted Lists (LeetCode 23, Heap Approach)

ListNode mergeKLists(ListNode[] lists) {
    // Min-Heap: prioritize nodes with smaller values
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode head : lists) {
        if (head != null) minHeap.offer(head);
    }

    ListNode dummy = new ListNode(0), cur = dummy;
    while (!minHeap.isEmpty()) {
        cur.next = minHeap.poll();
        cur = cur.next;
        // Re-inject the next node from the extracted list segment
        if (cur.next != null) minHeap.offer(cur.next);
    }
    return dummy.next;
}

Ugly Number II (LeetCode 264)

Three Pointers vs. Min-Heap. The three-pointers approach is generally faster (O(n)).

// Three-Pointers Approach (O(n), Recommended)
int nthUglyNumber(int n) {
    int[] ugly = new int[n];
    ugly[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    
    for (int i = 1; i < n; i++) {
        int next = Math.min(ugly[p2] * 2, Math.min(ugly[p3] * 3, ugly[p5] * 5));
        ugly[i] = next;
        
        // Progress pointers when their respective product is selected
        if (next == ugly[p2] * 2) p2++;
        if (next == ugly[p3] * 3) p3++;
        if (next == ugly[p5] * 5) p5++;
    }
    return ugly[n - 1];
}

Priority Queue API Reference

// Initialization
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Natural Order
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<int[]> customHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);

// Operations
minHeap.offer(x);   // Insert element (O(log N))
minHeap.peek();     // View top (root) without removing (O(1))
minHeap.poll();     // Extract top (root) (O(log N))
minHeap.size();
minHeap.isEmpty();