LeetCode Queue Design Patterns in C++: Put the Answer at an Edge

LeetCode Queue Design Patterns in C++: Put the Answer at an Edge

nycomdorics.com · preview of the WordPress post · source deck by Joseph Choi

A binary heap will hand you its smallest element instantly and tell you nothing whatsoever about the second smallest. A std::vector will append and remove at the back in constant time and charge you a full shift to remove from the front. Every structure in this family is generous at its edges and useless in its interior.

So the design job is always the same: arrange the data so that the value you need is sitting at an edge, and then move the markers instead of the elements. That is the whole idea behind a ring buffer, behind the two-heap median trick, behind a monotonic deque, and behind implementing a queue out of two stacks.

There is a second thing all of these share, and it is the part that actually decides whether your implementation is correct. Each design has exactly one ambiguous state, a moment where two different situations look identical from the inside. Choosing how to represent that state is the design. Everything else is bookkeeping.

The two problems at the core of this post come from a session deck by Joseph Choi. I compiled and tested every solution here under -fsanitize=undefined,address before writing about it, the deck’s own code included. Both of its solutions are correct. The four additional problems are mine, added because they are what makes the pattern visible: one shows the same trick with different containers, one shows where a single heap is already enough, one shows the design breaking down and needing a repair, and one shows it applied to a sliding window instead of a stream.

#	Problem	Difficulty	Source	The one ambiguous state
622	Design Circular Queue	Medium	deck	head == tail: one element, or full?
232	Implement Queue using Stacks	Easy	added	when has the output stack gone stale?
295	Find Median from Data Stream	Hard	deck	an even count has no single middle
703	Kth Largest Element in a Stream	Easy	added	fewer than k values seen so far
480	Sliding Window Median	Hard	added	is the heap’s top live, or already evicted?
239	Sliding Window Maximum	Hard	added	which candidates can still win?

---

Edges are cheap, middles are not

Before the problems, the deficit. Every container below is fast somewhere and slow everywhere else, and the pattern is nothing more than exploiting the fast part.

Structure	Constant time at	Expensive
std::vector	the back	the front (shifts every element), the middle
ring buffer over a vector	both ends	the middle
two stacks facing each other	the top of each	anything below a top
binary heap	one extreme	everything else, including the other extreme
two heaps back to back	the boundary between them	the actual extremes
monotonic deque	both ends	the middle

The fourth row is the one people underrate. A min-heap is not a sorted container. It knows its minimum and it knows essentially nothing else, which is exactly why the deck asks, when it gets to the median problem, whether one priority queue could possibly be enough.

---

LC 622 — move the indices, not the data

The deck starts by rejecting the easy answer, and the reasoning is worth repeating because it is the sort of thing that separates a passing submission from a good interview answer. A linked list gives you a queue immediately: push at the tail, pop at the head, both O(1), no wraparound to think about. The deck’s objection is that every node is a separate allocation at an unrelated address, so you pay an allocator call per element and you throw away memory locality. The problem statement even names the alternative for you: a ring buffer.

An array has the locality but the wrong operation. Removing from the front of an array means shifting everything left, which is O(n) per pop. The fix is to stop moving elements and start moving the boundary. The front of the queue is wherever head says it is, and when head runs off the end of the storage it wraps to zero. Nothing is copied; an index is incremented.

The ambiguous state

Track a head and a tail index and you hit the problem immediately. Suppose head == tail. Does that mean the queue holds one element, or is it coincidence, and the queue is empty? Both look identical. There are three standard resolutions:

1. Waste a slot. Never let the queue hold more than k - 1 elements, so head == tail can only mean empty. Costs you one slot and an allocation of k + 1.
2. Use a sentinel. Pick an index value that cannot be real, such as -1, and set head to it whenever the queue empties. This is the deck’s choice.
3. Store a count. Keep the number of live elements. Then empty and full are just count == 0 and count == k, and no comparison of indices is ever needed.

The deck’s sentinel version is correct. I ran it against std::deque over 144,000 random operation sequences across capacities 1 through 6 and it matches on every call, including the awkward k == 1 case where a single slot is simultaneously the head and the tail. Its isFull is the interesting line:

bool isFull() { return (tail + 1 == head) || (head == 0 && tail == q.size() - 1); }

That is a correct case split. Full means (tail + 1) % k == head. If tail + 1 < k the modulo does nothing and the first clause covers it; if tail + 1 == k the modulo yields 0 and the second clause covers it. There is no third case. It just takes a minute of staring to be sure of that, which is the argument for the count version below.

The count version

Storing a count removes the ambiguity rather than encoding around it, and it removes the tail index entirely, since the back of the queue is derivable from the front plus the length.

class MyCircularQueue {
    std::vector<int> buf;
    int head = 0;      // index of the front element
    int count = 0;     // how many slots are live
public:
    explicit MyCircularQueue(int k) : buf(k) {}

    bool enQueue(int value) {
        if (isFull()) return false;
        buf[(head + count) % capacity()] = value;   // one past the last live slot
        ++count;
        return true;
    }
    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % capacity();
        --count;
        return true;
    }
    int Front() const { return isEmpty() ? -1 : buf[head]; }
    int Rear()  const { return isEmpty() ? -1 : buf[(head + count - 1) % capacity()]; }
    bool isEmpty() const { return count == 0; }
    bool isFull()  const { return count == capacity(); }
private:
    int capacity() const { return static_cast<int>(buf.size()); }
};

Three things this buys. Every predicate becomes a comparison of two integers you already track, so there is no case analysis to get wrong. Every accessor can be const, which the deck’s version cannot be because isEmpty and isFull are not marked. And the capacity() helper returns an int, which quietly fixes a warning discussed in the traps section.

The cost is one extra integer of state. On a structure this small that is not a real trade, but it is worth knowing that in a lock-free single-producer single-consumer ring buffer the calculation flips: two independent indices can be updated by two threads without a shared counter, and a shared count becomes a contention point. That is why production ring buffers usually look more like the deck’s version than like this one.

---

LC 232 — the same idea with two stacks

Not in the deck, but it belongs here, because it solves the identical problem with entirely different parts and makes the pattern visible. A stack is cheap at exactly one end. A queue needs two cheap ends. Point two stacks at each other and the second one holds the first one in reverse, so its top is the oldest element.

The ambiguous state

When do you move elements from the input stack to the output stack? Move them on every push and you have rebuilt an O(n) queue. Move them at the wrong moment and you interleave old and new elements, and the FIFO order is silently wrong. The resolution is a single rule: refill the output stack only when it is completely empty.

class MyQueue {
    std::stack<int> in;    // newest on top
    std::stack<int> out;   // oldest on top
    void shift() {
        if (!out.empty()) return;                  // only refill when out is exhausted
        while (!in.empty()) { out.push(in.top()); in.pop(); }
    }
public:
    void push(int x) { in.push(x); }
    int pop()  { shift(); int v = out.top(); out.pop(); return v; }
    int peek() { shift(); return out.top(); }
    bool empty() const { return in.empty() && out.empty(); }
};

The amortised argument is the point of the problem. Any individual pop can be O(n), because it might trigger a full transfer. But each element is pushed onto in exactly once, moved to out exactly once, and popped exactly once, so its whole lifetime costs three stack operations regardless of how the calls are interleaved. I instrumented the transfer loop over 50,000 pushes and 50,000 pops with the operations mixed together:

LC 232, 50000 pushes and 50000 pops
  elements moved between stacks: 50000  (1.00 per element -> amortised O(1))

Exactly one move per element, which is the bound the follow-up asks you to argue for.

---

LC 295 — turning a middle into two edges

The deck asks the right question and answers it in one line: will a single priority queue be enough? No, because it only tells you a minimum or a maximum, and the median is neither. A heap is generous at exactly one edge, and the median lives in the interior, which is the one place no heap can reach.

The move is to stop trying to reach the middle and instead put the middle at an edge. Split the values into a smaller half and a larger half. Keep the smaller half in a max-heap, so its top is the largest of the small values. Keep the larger half in a min-heap, so its top is the smallest of the large values. Those two tops are precisely the two elements that straddle the median, and both are now edges.

The ambiguous state

An even number of elements has no single middle, so the two halves are the same size and the median is the average of the two tops. An odd number has a genuine middle, and it has to live in one heap or the other. Which one is a free choice, but it must be made once and enforced everywhere. The convention here is that lower always holds the extra element, which makes the invariant:

0 <= lower.size() - upper.size() <= 1

Everything in addNum exists to restore that inequality, and findMedian is a direct reading of it.

class MedianFinder {
    std::priority_queue<int> lower;                                            // max-heap: smaller half
    std::priority_queue<int, std::vector<int>, std::greater<int>> upper;       // min-heap: larger half
public:
    void addNum(int num) {
        lower.push(num);            // park it in lower...
        upper.push(lower.top());    // ...and hand lower's largest over to upper
        lower.pop();
        if (lower.size() < upper.size()) {   // lower keeps the extra element
            lower.push(upper.top());
            upper.pop();
        }
    }
    double findMedian() const {
        if (lower.size() > upper.size()) return lower.top();
        return (static_cast<double>(lower.top()) + upper.top()) / 2.0;
    }
};

Why push and transfer instead of comparing first

The three lines at the top of addNum look wasteful. You push the new value into lower only to immediately move lower‘s maximum into upper. The obvious alternative is to compare first and route the value to the correct heap directly.

The deck’s version has a real advantage: it cannot get the routing wrong. Pushing then transferring guarantees the new value lands in the correct half no matter what it is, because whichever value is largest in the smaller half after the insertion is by definition the one that belongs in the larger half. The comparison version has to special-case an empty heap, since lower.top() on an empty priority_queue is undefined behaviour, and forgetting that guard is a common way to fail this problem.

The cost is real but small. I counted every push, pop and top across 50,000 addNum calls on uniformly random values:

LC 295, 50000 addNum calls
  deck (push-then-transfer) : 275000 heap ops  (5.50 per call)
  compare-first             : 174591 heap ops  (3.49 per call)

Both are O(log n) per insertion. The constant factor is about 1.6x, which matters in a hot loop and does not matter on the judge. In an interview I would write the deck’s version, say out loud that comparing first saves roughly a third of the heap traffic at the cost of an emptiness check, and let the interviewer choose.

One more line worth defending. findMedian divides by 2.0 and not by 2. Dividing two ints by 2 gives you integer division, so the median of [2, 3] comes back as 2 instead of 2.5. It is the single most common wrong answer on this problem.

---

LC 703 — when one heap really is enough

The deck’s rhetorical question deserves a proper answer, because “a single priority queue is not enough” is true for the median and false in general. A single heap is enough whenever the value you want sits at a fixed offset from an edge, because you can throw away everything past that offset and the value you want becomes the edge.

The kth largest element is exactly that. Keep a min-heap that never exceeds k elements. Anything smaller than all k survivors cannot be the kth largest now or ever, so evicting it loses nothing. The smallest of the k largest is the kth largest, and it is sitting at the top.

class KthLargest {
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;   // the k largest so far
    int k;
public:
    KthLargest(int k, std::vector<int>& nums) : k(k) { for (int x : nums) add(x); }

    int add(int val) {
        heap.push(val);
        if (static_cast<int>(heap.size()) > k) heap.pop();   // evict the smallest survivor
        return heap.top();                                   // kth largest sits at the top
    }
};

The min-heap is the counterintuitive part. You are asked for a large element and you reach for the structure that surfaces small ones. That is correct precisely because you need cheap access to the worst of the elements you are keeping, so you can decide what to discard. Contrast this with the median, where no fixed offset from either edge locates the answer, since the target position moves as the stream grows. That is the real reason one heap fails there and two succeed.

The static_cast<int> on heap.size() is not decoration. size() returns an unsigned type, and comparing it against a signed k is a -Wsign-compare warning. Here it cannot misbehave, but the habit is worth having.

---

LC 480 — where two heaps stop working

Now push the median problem one step further. Instead of a stream that only grows, slide a window of size k across an array, so every step adds one value and removes another. The two-heap structure is still the right shape, and it breaks anyway.

It breaks because a heap supports removal at its top and nowhere else. The value falling out of the window is at an arbitrary depth. There is no operation for that, and searching the underlying vector is O(k) per step, which throws away everything the heap was buying you.

The ambiguous state

The repair is lazy deletion, and it introduces the sharpest ambiguity in this post. You do not remove the departing value at all. You record that you owe a deletion for it, leave it sitting in the heap as a ghost, and discard it only if it ever reaches the top, where removal is cheap. Now every heap contains a mixture of live values and ghosts, and the same question applies to every read: is the top of this heap real?

Two mechanisms resolve it. A delayed map counts how many deletions each value still owes. And the sizes used for balancing are tracked separately as smallSize and largeSize, counting only live values, because small.size() now counts ghosts too and is useless for deciding balance.

class WindowMedian {
    std::priority_queue<int> small;                                          // max-heap: lower half
    std::priority_queue<int, std::vector<int>, std::greater<int>> large;     // min-heap: upper half
    std::unordered_map<int,int> delayed;                                     // value -> deletions owed
    int smallSize = 0;                                                       // LOGICAL sizes, no ghosts
    int largeSize = 0;
    int k;
public:
    explicit WindowMedian(int k) : k(k) {}

    void add(int num) {
        if (small.empty() || num <= small.top()) { small.push(num); ++smallSize; }
        else                                     { large.push(num); ++largeSize; }
        rebalance();
    }
    void remove(int num) {
        ++delayed[num];                                  // mark it dead; never search for it
        if (num <= small.top()) { --smallSize; if (num == small.top()) prune(small); }
        else                    { --largeSize; if (num == large.top()) prune(large); }
        rebalance();
    }
    double median() const {
        if (k & 1) return small.top();
        return (static_cast<double>(small.top()) + large.top()) / 2.0;
    }
private:
    template <class PQ>
    void prune(PQ& pq) {                                 // strip dead values off the top only
        while (!pq.empty()) {
            int v = pq.top();
            auto it = delayed.find(v);
            if (it == delayed.end()) break;
            if (--(it->second) == 0) delayed.erase(it);
            pq.pop();
        }
    }
    void rebalance() {
        if (smallSize > largeSize + 1) {
            large.push(small.top()); small.pop(); --smallSize; ++largeSize; prune(small);
        } else if (smallSize < largeSize) {
            small.push(large.top()); large.pop(); ++smallSize; --largeSize; prune(large);
        }
    }
};

std::vector<double> medianSlidingWindow(std::vector<int>& nums, int k) {
    WindowMedian window(k);
    for (int i = 0; i < k; ++i) window.add(nums[i]);
    std::vector<double> out{window.median()};
    for (int i = k; i < static_cast<int>(nums.size()); ++i) {
        window.add(nums[i]);
        window.remove(nums[i - k]);
        out.push_back(window.median());
    }
    return out;
}

The invariant that keeps this honest is that the top of each heap is always live. Every operation that could expose a ghost at a top calls prune immediately afterwards, which is why prune appears inside rebalance as well as inside remove. Given that invariant, the branch in remove is safe: a value in the window is either at most small.top() or at least large.top(), and nothing can sit strictly between the two tops.

Note also that the window size is fixed, so median() can branch on the parity of k rather than on the current sizes. That is a small simplification the streaming version does not get.

I tested this against brute-force sorting of every window over 3,000 random arrays with heavy duplication, which is the case lazy deletion is most likely to mishandle, since the delayed map is keyed by value and not by position.

---

LC 239 — the deque version of the same move

One last variation, because it shows the pattern without any heaps at all. Sliding window maximum looks like it needs a heap, and a heap with lazy deletion does solve it. But there is a better structure, and finding it comes from one observation: if a value enters the window and it is larger than something already in the window to its left, that older, smaller value can never be the maximum again. It is younger and bigger, so it will outlive its rival and beat it the whole time.

So you can throw those losers away permanently. What remains is a deque of indices whose values strictly decrease from front to back. The front is the current maximum, and the front is an edge.

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::deque<int> idx;            // indices, values strictly decreasing front to back
    std::vector<int> out;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        if (!idx.empty() && idx.front() <= i - k) idx.pop_front();           // fell out of window
        while (!idx.empty() && nums[idx.back()] <= nums[i]) idx.pop_back();  // can never win again
        idx.push_back(i);
        if (i >= k - 1) out.push_back(nums[idx.front()]);
    }
    return out;
}

Store indices, not values, or you cannot tell when the front has aged out of the window. The expiry check is an if and not a while because the window advances by one position per iteration, so at most one index can expire per step. The eviction check is a while because a single large value can dominate many predecessors at once.

This is O(n) overall, not O(n log k), because each index is pushed once and popped once. The two-heap and lazy-deletion machinery from LC 480 is not needed here, which is a good reminder that reaching for the heaviest correct structure is its own kind of mistake.

---

Traps, with the demonstrations

Everything in this section was reproduced on a compiler rather than recalled.

The same median line, two problems, one overflow

LC 295 and LC 480 both end in an average of two ints. The deck writes it the natural way, and for LC 295 the natural way is correct:

return (lowerHalf.top() + upperHalf.top()) / 2.0;   // int + int, then convert

LC 295 constrains values to the range -10⁵ to 10⁵, so the sum tops out around 2 × 10⁵ and fits comfortably. LC 480 constrains nums[i] to the full signed 32-bit range, -2³¹ to 2³¹ – 1. Same line, different outcome:

=== the same median line under two different constraints ===
LC 295 range (|num| <= 1e5):   lo=100000  hi=100000
   (lo + hi) / 2.0        = 100000.0
LC 480 range (full int):       lo=2147483647  hi=2147483646
runtime error: signed integer overflow: 2147483647 + 2147483646
               cannot be represented in type 'int'

Converting one operand first, (static_cast<double>(a) + b) / 2.0, promotes the whole expression and costs nothing. This is why the code above uses that form in both classes even though only one of them needs it: the habit is cheaper than remembering which problem has which constraint.

findMedian() before any addNum()

If both heaps are empty, lower.size() > upper.size() is false, so the code takes the even branch and calls top() on two empty heaps. That is undefined behaviour. LC 295 guarantees at least one element before findMedian is called, so it never fires on the judge, but the standard library will tell you about it if you ask. Compiled with -D_GLIBCXX_ASSERTIONS:

sizes are 0 and 0; the deck takes the even branch and calls top() on both
/usr/include/c++/13/bits/stl_queue.h:725: ...priority_queue<...>::top() const:
    Assertion '!this->empty()' failed.

Turning that flag on for a debug build is a cheap habit. It catches this class of mistake across the whole standard library, not just here.

The signed comparison in isFull

The deck’s isFull compares an int against a size_t:

warning: comparison of integer expressions of different signedness:
         'int' and 'std::vector<int>::size_type' [-Wsign-compare]
   return (tail + 1 == head) || (head == 0 && tail == q.size() - 1);

I want to be accurate about this one: it is a warning, not a bug. When the queue is empty tail is -1, and converting -1 to an unsigned type yields an enormous number, but the comparison still evaluates to false and the head == 0 clause short-circuits before it anyway. I tried to construct an input where it misbehaves and could not. Fix it because warnings you have decided to ignore are how the real ones hide, not because this one bites.

Where % by a container size does bite

The genuinely fragile line in the deck’s version is tail %= q.size(). LC 622 guarantees k >= 1, so on the judge this is fine. Reuse the class anywhere else with a zero capacity and it is an integer division by zero. The count version never divides by anything it has not already compared against, so it degrades into a permanently-full zero-capacity queue instead:

--- count-based version with k = 0 ---
isFull=1 isEmpty=1 enQueue(7)=0  -> degrades cleanly
--- deck version with k = 0 ---
t622_edge.cpp:11:14: runtime error: division by zero
SUMMARY: AddressSanitizer: FPE in DeckQueue::enQueue(int)

This is outside the stated constraints and does not make the deck’s solution wrong. It is the kind of difference that shows up when a coding-interview class gets pasted into something real.

Smaller things worth checking

• Integer division in the median. (a + b) / 2 instead of (a + b) / 2.0 returns 2 for the median of [2, 3]. The return type being double does not save you; the division has already happened in int.
• Rear() without the empty guard. The deck guards it. Without the guard, q[tail] with tail == -1 is an out-of-bounds read that AddressSanitizer catches instantly and the judge may not.
• Comparing size() against a signed variable. Appears in LC 703 (heap.size() > k) and in the deck’s LC 622. Cast once, at the boundary, rather than at every use.
• Storing values instead of indices in LC 239. The window expiry check needs to know when a candidate entered, and a value cannot tell you that.
• Using small.size() for balancing in LC 480. After lazy deletion that number counts ghosts. The logical sizes have to be tracked by hand, and mixing the two up produces a structure that is balanced by physical size and wrong by logical size.

---

The pattern in one table

Problem	What sits at the edge	How the ambiguity is resolved
622	front and back of the ring	head = -1 sentinel, or a live-element count
232	top of each stack	refill the output stack only when it is empty
295	the two values straddling the median	lower always keeps the odd element
703	the smallest of the k largest	cap the heap at k and read its top
480	the same two values, plus ghosts	lazy deletion, with logical sizes tracked separately
239	the current window maximum	keep only indices whose values strictly decrease

When you meet a new problem in this family, the question that picks the structure is not “queue or heap or deque”. It is: what would have to be true for the answer to be sitting at an edge? Then arrange the data so that it is, and work out which state is ambiguous before you write a line of code. Both deck problems, and all four additions, fall out of those two questions.

---

Source and method

LC 622 and LC 295, and the reasoning that motivates both solutions, come from a queue session deck by Joseph Choi. Both of its implementations are correct as written; the rewrites above are about state representation and type hygiene, and each section says what the change buys. LC 232, 703, 480 and 239 are additions of mine, chosen to test the pattern rather than pad the list.

Every C++ snippet was compiled with g++ -std=c++20 -Wall -Wextra -Wpedantic and run under -fsanitize=undefined,address with leak detection enabled. LC 622 was checked against std::deque over 144,000 random operation sequences spanning capacities 1 to 6; LC 232 against std::deque; LC 295 against a sorted vector over 160,000 insertions drawn from the full stated value range; LC 703 against a sorted copy; LC 480 and LC 239 against brute force over 3,000 random arrays each with deliberately heavy duplication, plus a run at INT_MAX and INT_MIN. Operation counts and the amortised bound for LC 232 were measured by instrumenting the containers, not estimated.