Priority Queue and Monotonic Queue Patterns: Sliding Window Maximum, Top-K, and Scheduling (2025)

Sliding Window Maximum – Monotonic Deque (LC 239)

O(n) solution using a monotonic decreasing deque storing indices. Each element is added and removed at most once.

from collections import deque

def maxSlidingWindow(nums, k):
    """LC 239 - Sliding Window Maximum. O(n) time, O(k) space."""
    dq = deque()  # stores indices, front is always the max
    result = []

    for i, val in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order - remove smaller elements from back
        while dq and nums[dq[-1]] = k - 1:
            result.append(nums[dq[0]])
    return result

# nums = [1,3,-1,-3,5,3,6,7], k = 3
# Output: [3,3,5,5,6,7]

Key invariant: deque is always monotonically decreasing. Front element is always the window maximum. We never need an element smaller than a newer element – it can never be the maximum while that newer element is in the window.

Top-K Frequent Elements (LC 347)

Two approaches: bucket sort O(n) and min-heap O(n log k). Bucket sort wins for exact top-K when k is not small relative to n.

from collections import Counter
import heapq

def topKFrequent_bucket(nums, k):
    """Bucket sort approach - O(n) time and space."""
    count = Counter(nums)
    # Bucket index = frequency, max frequency  k:
            heapq.heappop(heap)
    return [num for freq, num in heap]

# When to use which:
# Bucket sort: when you need exactly top-K and n is manageable
# Heap: when k << n, streaming data, or memory is constrained

Ugly Numbers (LC 264)

Ugly numbers have only prime factors 2, 3, 5. Two approaches: O(n) three-pointer DP and O(n log n) min-heap.

import heapq

def nthUglyNumber_dp(n):
    """Three-pointer DP - O(n) time and space. Best approach."""
    ugly = [1] * n
    p2 = p3 = p5 = 0
    for i in range(1, n):
        next2 = ugly[p2] * 2
        next3 = ugly[p3] * 3
        next5 = ugly[p5] * 5
        ugly[i] = min(next2, next3, next5)
        if ugly[i] == next2: p2 += 1
        if ugly[i] == next3: p3 += 1
        if ugly[i] == next5: p5 += 1
    return ugly[n - 1]

def nthUglyNumber_heap(n):
    """Min-heap approach - O(n log n). Easier to generalize."""
    heap = [1]
    seen = {1}
    val = 1
    for _ in range(n):
        val = heapq.heappop(heap)
        for factor in [2, 3, 5]:
            nxt = val * factor
            if nxt not in seen:
                seen.add(nxt)
                heapq.heappush(heap, nxt)
    return val

# DP wins for fixed factors {2,3,5}
# Heap generalizes easily to arbitrary prime sets (Super Ugly Number LC 313)

Meeting Rooms II (LC 253)

Find minimum number of conference rooms required. Min-heap tracks end times of all ongoing meetings.

import heapq

def minMeetingRooms(intervals):
    """Min-heap of end times. O(n log n) time."""
    if not intervals:
        return 0
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    # Min-heap of end times of active meetings
    heap = []
    for start, end in intervals:
        if heap and heap[0]  2
# At time 5: rooms = [30, 10]. Room for [0,30] in use, new room for [5,10].
# At time 15: [5,10] ended, reuse that room for [15,20]. Rooms = [30, 20].

IPO – Two-Heap Greedy (LC 502)

Maximize capital after k projects. Greedy: always pick the highest-profit available project. Use a min-heap sorted by capital requirement and a max-heap of available profits.

import heapq

def findMaximizedCapital(k, w, profits, capital):
    """Two-heap greedy. O((n + k) log n) time."""
    # Min-heap by capital requirement (capital, profit)
    locked = sorted(zip(capital, profits))
    locked_idx = 0
    # Max-heap of available profits (negate for max-heap)
    available = []

    for _ in range(k):
        # Unlock all projects we can now afford
        while locked_idx < len(locked) and locked[locked_idx][0] <= w:
            cap, prof = locked[locked_idx]
            heapq.heappush(available, -prof)
            locked_idx += 1
        # No affordable project available
        if not available:
            break
        # Take the highest-profit available project
        w += -heapq.heappop(available)

    return w

# k=2, w=0, profits=[1,2,3], capital=[0,1,1]
# Round 1: can afford project 0 (cap=0), take profit 1. w=1.
# Round 2: can afford projects 1,2 (cap=1). Take profit 3. w=4.
# Output: 4

Pattern summary: two-heap greedy appears when you have items with a constraint (capital) and a value (profit), and you want to greedily maximize value while satisfying constraints in sequence. Similar structure to task scheduling problems.

Frequently Asked Questions

Why is the deque-based sliding window maximum O(n) when we loop over all elements?

Each element is pushed to the deque at most once and popped at most once, giving O(2n) = O(n) total operations. The inner while loop does not restart from the beginning – it only removes elements that are smaller than the current element, and those elements are gone permanently.

When should I use bucket sort vs heap for Top-K Frequent Elements?

Bucket sort is O(n) and always wins on time complexity for this specific problem. Use the heap approach when: k is very small relative to n (O(n log k) with small k), you are processing a data stream and cannot know n upfront, or memory is extremely constrained and you want to avoid the O(n) bucket array.

Why does the three-pointer approach beat the heap for Ugly Numbers?

Three pointers give O(n) time with O(n) space and no heap overhead. The heap approach is O(n log n) due to heap operations. The key insight is that you only need three pointers – one per prime factor – because each ugly number is generated by multiplying a previous ugly number by exactly 2, 3, or 5.

How does heapreplace differ from heappop + heappush in Meeting Rooms II?

heapreplace(heap, item) is a single O(log n) operation that atomically pops the smallest element and pushes the new item. Using heappop followed by heappush would be two separate O(log n) operations. heapreplace is also slightly faster because it avoids the extra sift-up that happens when the new item is larger than the popped item.

What makes the two-heap approach for IPO correct – why is greedy valid here?

The greedy is valid because capital earned is additive and projects do not expire. Taking the highest-profit available project now never blocks a better future choice – it only increases your capital, unlocking more projects. This is the “exchange argument”: swapping any non-greedy choice with the greedy choice cannot decrease the final capital.