Stacks, binary search, heaps and greedy algorithms

Before this lesson: lesson 01 (the routine, the cost of Python operations, two pointers). Time: about 90 minutes, plus the notebook. This lesson is long: take a break after section 3.3 (binary search).

Why this matters #

These patterns appear in most coding interviews, and in each one the code is short but the reasoning is not. Interviewers ask "why is this loop $O(n)$?", "why mid + 1 and not mid?", "why a min-heap for the largest items?" and "why is the greedy correct?". A clear invariant answers each question. The same tools run inside ML systems: reverse-mode autodiff runs the backward pass from a stack of recorded operations (last in, first out), np.searchsorted places values into bins by binary search, beam search keeps the best $B$ hypotheses, vector search keeps the $k$ nearest neighbours in a heap, and job schedulers sort and sweep intervals of time.

1. Predict first #

2. The picture #

The stack: the last open item closes first. In ( [ ] ), the ] must match the most recent bracket that is still open. A stack is a list where you add (push) and remove (pop) only at one end, the top: last in, first out. With one bracket type, a counter of open brackets is enough. With several types, ( [ ) ] has balanced counts but is wrong. You must remember the order of the open brackets, and that is what a stack stores.

The monotonic stack: wait until you are answered. Take the temperatures [73, 74, 75, 71, 69, 72, 76, 73]. The brute force looks ahead from every day: $O(n^2)$. Instead, keep the days that still wait for a warmer day. Their temperatures never increase from the bottom to the top of the stack, because a warmer day would have answered a colder day below it and removed it. Day 5 (72) answers 69 and 71, which are on top, and stops at 75. Every day is pushed once and popped at most once.

Binary search: halve the range where the answer can be. Guess a number between 1 and 100 with questions "is it $\ge m$?". Each answer halves the candidates, so 7 questions are enough ($2^7 = 128 \ge 100$). This needs no sorted list, only a yes/no question whose answers are "no, …, no, yes, …, yes" along an ordered axis: the indices of a sorted list, or the possible answers themselves ("is speed $k$ fast enough?").

Heap: know only the minimum. A binary heap is a complete binary tree stored in a plain list. Every level is full except the last one, which fills from the left. In a min-heap a parent is never larger than its children. So the root holds the minimum, and the rest is only partly ordered. That is the point: you pay only for knowing the minimum, not for a full sort.

Intervals: sort once, then sweep. Draw the intervals on a time line. After you sort them by start, an interval can overlap only the block just before it, because every earlier interval started earlier. So you look at each interval once and compare it with one number: the end of the current block.

Greedy: choose, and never go back. A greedy algorithm builds the answer one choice at a time. It is correct when some optimal solution starts with the greedy choice: then the rest is a smaller copy of the same problem. If you cannot show this, the greedy is only a guess.

3. Definitions and main results #

3.1 The stack #

A stack supports push, pop (remove and return the top), top and is_empty. A Python list is a stack: append, pop() and [-1] cost $O(1)$ (append: amortized). pop(0) is $O(n)$, so never use it in a loop; a queue needs collections.deque.

Use a stack when an item is closed by the most recent unclosed item: brackets, nested strings like 3[a2[c]], "undo", or an operator that takes the last two operands (Reverse Polish notation, RPN: ["2", "1", "+", "3", "*"] means $(2 + 1) \cdot 3 = 9$). Any recursion can be written as a loop with an explicit stack. In Python this matters: the default recursion limit is 1,000 frames, so a recursive depth-first search on a path of $10^5$ nodes crashes.

def valid_brackets(s):
    match = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != match[ch]:   # nothing open, or the wrong type
            return False
    return not stack                                  # every bracket was closed

3.2 The monotonic stack #

Problem (next greater element). Given $a_0, \dots, a_{n-1}$, find for every index $j$ the smallest index $i > j$ with $a_i > a_j$, or "none".

Algorithm. Scan $i = 0, \dots, n-1$. While the stack is not empty and $a_{\text{top}} < a_i$: pop the top index $j$ and set $\text{answer}[j] = i$. Then push $i$. The indices left on the stack at the end get "none". Daily Temperatures is this problem with $\text{answer}[j] = i - j$ (and 0 for "none").

Theorem 1 (monotonic stack). The algorithm is correct. It does $n$ pushes, at most $n$ pops and at most $2n$ comparisons: $O(n)$ time and $O(n)$ extra space, although a while loop sits inside the for loop.

Invariant. Before step $i$: (a) the stack holds exactly the indices $j < i$ that have no greater element in $a_{j+1}, \dots, a_{i-1}$; (b) their values do not increase from the bottom to the top.

Proof.

1. Before step 0 the stack is empty and there is no index $j < 0$, so the invariant holds.
2. Step $i$ pops indices $j$ with $a_j < a_i$. By (a), no element between $j$ and $i$ is greater than $a_j$, so $i$ is the first greater element: $\text{answer}[j] = i$ is correct.
3. By (b), the indices with $a_j < a_i$ form a block at the top. So "pop while the top is smaller" removes exactly them, and it stops at a top with $a_{\text{top}} \ge a_i$.
4. The indices that stay still have no greater element up to $i$, and $i$ has none yet. Pushing $i$ on top of a value $\ge a_i$ keeps (b). So the invariant holds before step $i + 1$. After the last step it says that the indices left have no greater element.
5. Cost (an amortized bound): each index is pushed once and popped at most once. One step can pop many indices, but the whole run pops at most $n$. Each comparison either causes a pop or ends a while loop (at most one per step). So there are at most $2n$ comparisons. $\blacksquare$

Variants. Change the comparison:

One pass gives two answers: $i$ is the next element of every index it pops, and the top left after the pops is the previous element of $i$. A monotonic deque does the same on a sliding window: pop smaller values from the back, and pop the front when its index leaves the window. It gives the maximum of every window of size $k$ in $O(n)$ (Sliding Window Maximum).

def largest_rectangle(h):
    stack, best = [], 0                      # indices with increasing heights
    for i, x in enumerate(h + [0]):          # a final 0 pops everything
        while stack and h[stack[-1]] >= x:
            j = stack.pop()
            left = stack[-1] if stack else -1
            best = max(best, h[j] * (i - left - 1))
        stack.append(i)
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))   # 10  (height 5, width 2)

3.3 Binary search, correct by construction #

A predicate $P$ maps integers to {False, True}. It is monotone on $[L, R)$ if $P(k)$ True implies $P(k+1)$ True, so its values are False, …, False, True, …, True. We want the first True $k^*$, or $R$ if all values are False.

The template (half-open range $[lo, hi)$).

def first_true(P, L, R):
    lo, hi = L, R
    while lo < hi:
        mid = (lo + hi) // 2      # lo <= mid < hi
        if P(mid):
            hi = mid              # mid may be the first True: keep it in the range
        else:
            lo = mid + 1          # mid is False, so the first True is after it
    return lo

Theorem 2 (binary search). For a monotone $P$ and $R > L$, the template returns $k^*$ after at most $\lfloor \log_2 (R - L) \rfloor + 1$ calls of $P$.

Invariant. $P(k)$ is False for every $k$ in $[L, lo)$ and True for every $k$ in $[hi, R)$. (We treat $R$ itself as True.)

Proof.

1. At the start both ranges are empty, so the invariant holds.
2. In the loop $lo < hi$, so $lo \le mid < hi$: mid is always inside the open range.
3. If $P(mid)$ is True, monotonicity makes $P$ True on $[mid, R)$, so hi = mid keeps the invariant. If it is False, monotonicity makes $P$ False on $[L, mid]$, so lo = mid + 1 keeps it.
4. Let $s = hi - lo$. The new size is $\lfloor s/2 \rfloor$ (after hi = mid) or $\lceil s/2 \rceil - 1$ (after lo = mid + 1); both are at most $\lfloor s/2 \rfloor$. So the loop ends after at most $\lfloor \log_2 (R - L) \rfloor + 1$ iterations.
5. At the end $lo = hi$: everything before $lo$ is False and everything from $lo$ on is True, so $lo = k^*$. $\blacksquare$

The invariant decides every detail: < versus <= in the loop, mid versus mid + 1, and the return value. Choose one range style and keep it.

Instances.

• Sorted list $a$: $P(i) = (a_i \ge x)$ gives the lower bound (bisect.bisect_left), the first position where $x$ could be inserted. $P(i) = (a_i > x)$ gives bisect_right. Their difference counts the copies of $x$.
• Binary search on the answer. $P(k)$ = "$k$ is enough" (a speed, a capacity, a time). It is monotone when more is never worse. Example (Koko Eating Bananas): piles [3, 6, 7, 11] and $h = 8$ hours; at speed $k$ a pile of $p$ bananas takes $\lceil p/k \rceil$ hours. "$k$ is enough" means $\sum_p \lceil p/k \rceil \le h$. Search $k$ in $[1, \max p]$: the answer is 4. Cost: $O(\log(\text{range}) \cdot \text{cost of } P)$.
• Rotated sorted list (distinct values), for example [4, 5, 6, 7, 0, 1, 2]: $P(i) = (a_i \le a_{n-1})$ is False on the left block and True on the right block, so its first True is the minimum. To search for a value, note that one of the halves $[lo, mid]$ and $[mid, hi]$ is sorted; one range check tells whether the target can be in it.
• Real numbers (bisection): keep $P(lo)$ False and $P(hi)$ True, and stop when $hi - lo < \delta$. After $t$ steps the interval has length $(R - L)/2^t$.

When $P$ is not monotone. Monotonicity is used only in step 3 of the proof. Without it, the loop still ends, and it keeps a weaker invariant: $P(lo - 1)$ is False (or $lo = L$) and $P(hi)$ is True (or $hi = R$). So it returns some $k$ where $P$ switches from False to True, not necessarily the first. This can be useful: with $P(i) = (a_i > a_{i+1})$, "the list goes down after $i$", the switch point is a local peak (Find Peak Element).

3.4 The binary heap #

A list heap of length $n$ stores a complete binary tree: node $i$ has the children $2i + 1$ and $2i + 2$ and the parent $\lfloor (i - 1)/2 \rfloor$ (0-based, as in Python's heapq). The tree has height $\lfloor \log_2 n \rfloor$.

• Invariant (min-heap): heap[parent(i)] <= heap[i] for every $i \ge 1$. So heap[0] is the minimum.
• Push: append the new item, then sift up: swap it with its parent while it is smaller. At most one swap per level: $O(\log n)$.
• Pop: take heap[0], move the last item to the root, then sift down: swap it with its smaller child while that child is smaller. $O(\log n)$.
• Peek: heap[0] in $O(1)$. Any other item needs a search. For example, the maximum of a min-heap is in a leaf, one of the indices $\lfloor n/2 \rfloor, \dots, n-1$.

Theorem 3 (heapify is linear). Building a heap from $n$ items by sifting down every internal node, from the last one back to the root, costs $O(n)$.

Proof.

1. A sift-down that starts at a node of height $h$ (its distance to the lowest leaf below it) makes at most $h$ swaps.
2. A complete tree with $n$ nodes has at most $\lceil n / 2^{h+1} \rceil$ nodes of height $h$.
3. Heights run from 0 to $H = \lfloor \log_2 n \rfloor$. Add the bounds of steps 1 and 2 over all heights, and use $\lceil x \rceil \le x + 1$ and $\sum_{h \ge 0} h / 2^{h+1} = 1$.

Hence heapify costs $O(n)$. $\blacksquare$

In contrast, $n$ pushes cost $O(n \log n)$ in the worst case. In a sift-up, the many nodes near the bottom are the ones that can travel $\log_2 n$ levels. In a sift-down they travel only a few levels, and the leaves (half of all nodes) do not move at all.

Python details. heapq is a min-heap on a plain list. For a max-heap, push -x and negate again when you pop. Tuples compare field by field, so (priority, payload) compares the payloads when two priorities are equal, and this fails for dicts; push (priority, counter, payload) with a running counter instead. heapq.heapreplace(h, x) pops, then pushes (the result may be larger than x); heapq.heappushpop(h, x) pushes, then pops (it returns x at once if x is the smallest).

3.5 Top-$k$ #

To keep the $k$ largest items of a stream, keep a min-heap of size $k$. Its root is the weakest member of the current top $k$: the gatekeeper. A new item $x$ enters only if it beats the root, and then it replaces the root (heapreplace). Cost: $O(n \log k)$ time and $O(k)$ memory.

Merge $k$ sorted lists: keep a heap with the current head of each list; pop the smallest, push the next item of its list. $O(N \log k)$ for $N$ items in total (heapq.merge does this).

3.6 Intervals #

An interval is a pair $[s, e]$ with $s \le e$. Say which convention you use, because it decides the edge cases:

• closed $[s, e]$: $a$ and $b$ overlap when $a_s \le b_e$ and $b_s \le a_e$, so $[1, 4]$ and $[4, 5]$ overlap;
• half-open $[s, e)$, the usual one for meetings: they overlap when $a_s < b_e$ and $b_s < a_e$, so back-to-back meetings do not overlap.

Lemma (merging after a sort by start). Sort by start and keep the current block $[S, E]$. If the next interval has $s > E$, then no later interval overlaps the block either, because every later start is $\ge s > E$. So the block is final, and one pass merges everything: $O(n \log n)$ for the sort plus $O(n)$ for the pass. The update is $E = \max(E, e)$, not $E = e$, because a short interval can sit inside a long one.

Meeting rooms. The fewest rooms that hold all meetings equals the depth: the largest number of meetings that are in progress at one moment. Sweep over the $2n$ events sorted by time: $+1$ at each start, $-1$ at each end. With half-open meetings, an end at time $t$ comes before a start at the same time $t$. The largest running count is the depth. (Equivalent: sort by start and keep a min-heap of the end times of the rooms in use.)

3.7 Greedy algorithms and the exchange argument #

A greedy algorithm builds a solution by a sequence of locally best choices and never revisits them. The classic example is interval scheduling: choose the largest set of pairwise non-overlapping intervals.

Theorem 4 (interval scheduling). For intervals $[s, e)$ with $s < e$, sort them by end and take each interval that starts at or after the end of the last one taken. The result is a largest set of non-overlapping intervals. Time $O(n \log n)$.

Proof (exchange argument, then induction).

1. Let $g$ be the interval with the smallest end. Let $O$ be any optimal set, and $o$ the interval of $O$ with the smallest end.
2. $g$ ends no later than $o$. Every other interval of $O$ starts at or after the end of $o$, so it also starts at or after the end of $g$.
3. So $O' = (O \setminus \{o\}) \cup \{g\}$ has no overlap and the same size: some optimal set contains $g$.
4. After taking $g$, the remaining candidates are the intervals that start at or after the end of $g$. This is the same problem on fewer intervals. By induction, the greedy solves it optimally. $\blacksquare$

Two proof templates cover most interview greedy problems:

• Exchange argument: take any optimal solution and swap the greedy choice into it without making it worse (the proof above).
• Greedy stays ahead: show by induction that after each step the greedy partial solution is at least as good as any other, measured by one number. For interval scheduling: the $j$-th interval taken by the greedy ends no later than the $j$-th interval of any valid schedule.

Two one-pass greedy problems and their key facts.

• Jump Game. nums[i] is the longest jump from index $i$; can you reach the last index? Keep reach = the furthest index reachable so far. Key fact: the reachable indices always form a prefix $[0, \text{reach}]$, because from any reachable index you can also stop earlier. So the answer is False exactly when some $i > \text{reach}$. For [3, 2, 1, 0, 4], reach stays 3 and index 4 is never reached.
• Gas Station. Stations on a circle with gas $g_i$ and cost $c_i$ to drive to the next one. Key lemma: if you start at $a$ with an empty tank and the gas first runs out on the way from station $b$ to station $b + 1$, then no station from $a$ to $b$ can be a start either (you arrived at each of them with gas $\ge 0$, and starting there empty only gives less). So restart at $b + 1$. A solution exists exactly when $\sum_i g_i \ge \sum_i c_i$.

Many problems look greedy and are not. With coins $\{1, 3, 4\}$ and amount 6, "largest coin first" gives $4 + 1 + 1$ (3 coins), but $3 + 3$ uses 2. That problem needs dynamic programming (lesson 04). Before you trust a greedy, compare it with a brute force on many tiny random inputs.

Answers to section 1. (1) No. Each index is pushed once and popped at most once, so the whole run does at most $n$ pops and $2n$ comparisons: $O(n)$ (Theorem 1, step 5). (2) A min-heap of size 10. Its root is the 10th largest number so far; each new number is compared with the root and replaces it if it is larger. The cost is $O(n \log k)$ with $k = 10$, and the memory is $O(k)$. A max-heap of everything would need memory for all $10^9$ numbers. (3) Earliest end first (Theorem 4). Earliest start fails on $[0, 10), [1, 2), [3, 4)$: it takes $[0, 10)$ and nothing else, but two meetings fit. Shortest first fails on $[0, 5), [4, 7), [6, 11)$: it takes $[4, 7)$, which blocks both others, but $[0, 5)$ and $[6, 11)$ fit together.

4. Worked example #

(a) A monotonic stack: stock spans. For each day, the span is the number of consecutive days, ending today, with a price $\le$ today's price. This is "previous strictly greater" from the variants table: pop while $\text{price}_{\text{top}} \le p$; then the span is $i - \text{top}$, or $i + 1$ if the stack is empty. Prices [100, 80, 60, 70, 60, 75, 85]:

Spans: [1, 1, 1, 2, 1, 4, 6]. Day 5 pops two days at once, but the whole run has 7 pushes and only 5 pops.

(b) Binary search on the answer: the integer square root. Find the largest $r$ with $r^2 \le 30$. Use $P(k) = (k^2 > 30)$, which is monotone, on $[0, 31)$; then $r = k^* - 1$.

The loop stops with $lo = hi = 6$, so $k^* = 6$ and $r = 5$, after $5 = \lfloor \log_2 31 \rfloor + 1$ calls of $P$.

(c) A heap by hand. Push 5, 3, 8, 1 into an empty min-heap.

• Push 5: [5].
• Push 3: [5, 3]. 3 is smaller than its parent 5, so swap: [3, 5].
• Push 8: [3, 5, 8]. 8 is larger than its parent 3, so stop.
• Push 1: [3, 5, 8, 1] (index 3, parent index 1). 1 < 5, swap: [3, 1, 8, 5]. 1 < 3, swap: [1, 3, 8, 5].

Pop: return 1. Move the last item, 5, to the root: [5, 3, 8]. The children of index 0 are 3 and 8; the smaller one, 3, is less than 5, so swap: [3, 5, 8]. Index 1 has no child ($2 \cdot 1 + 1 = 3 \ge 3$), so stop. Result: [3, 5, 8].

(d) Interval scheduling by hand. The intervals $[1,3], [2,4], [3,5], [0,7], [5,8], [6,9], [8,10]$ (touching allowed) are already sorted by end.

Four intervals are kept, so the fewest removals that leave no overlap is $7 - 4 = 3$. A brute force over all $2^7 = 128$ subsets agrees.

5. In code #

Templates for problems that are not the notebook exercises, each checked against a brute force on random inputs.

import heapq
import math
import random
from collections import Counter
from itertools import combinations


def stock_spans(prices):
    """span[i] = number of consecutive days ending at day i with a price <= prices[i]. O(n)."""
    spans, stack = [], []         # stack: indices with strictly decreasing prices
    for i, p in enumerate(prices):
        while stack and prices[stack[-1]] <= p:   # these days can never end a later span
            stack.pop()
        spans.append(i - stack[-1] if stack else i + 1)
        stack.append(i)
    return spans


def isqrt(x):
    """The largest integer r with r*r <= x, for an int x >= 0. O(log x) steps."""
    lo, hi = 0, x + 1             # search [0, x+1) for the first k with k*k > x
    while lo < hi:
        mid = (lo + hi) // 2
        if mid * mid > x:
            hi = mid
        else:
            lo = mid + 1
    return lo - 1


def find_peak(nums):
    """An index i with nums[i] > both neighbours (outside: -inf). Neighbours differ. O(log n)."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[mid + 1]:   # going down after mid: a peak at mid or on its left
            hi = mid
        else:                           # going up after mid: a peak on its right
            lo = mid + 1
    return lo


def top_k_frequent(nums, k):
    """The k most frequent values: a min-heap of size k over (count, value). O(n log k)."""
    heap = []
    for value, count in Counter(nums).items():
        if len(heap) < k:
            heapq.heappush(heap, (count, value))
        elif count > heap[0][0]:               # beats the gatekeeper
            heapq.heapreplace(heap, (count, value))
    return [v for _, v in heap]


def min_removals(intervals):
    """Fewest removals so that the rest do not overlap (touching allowed): sort by END."""
    kept, last_end = 0, -math.inf
    for s, e in sorted(intervals, key=lambda iv: iv[1]):
        if s >= last_end:
            kept, last_end = kept + 1, e
    return len(intervals) - kept


# Brute-force references
def brute_spans(prices):
    out = []
    for i, p in enumerate(prices):
        j = i
        while j >= 0 and prices[j] <= p:
            j -= 1
        out.append(i - j)
    return out


def brute_removals(intervals):
    n = len(intervals)
    for size in range(n, -1, -1):
        for sub in combinations(sorted(intervals), size):
            if all(a[1] <= b[0] for a, b in zip(sub, sub[1:])):
                return n - size


rng = random.Random(0)
for _ in range(2000):
    prices = [rng.randint(1, 6) for _ in range(rng.randint(0, 12))]
    assert stock_spans(prices) == brute_spans(prices)
    x = rng.randint(0, 10**30)
    assert isqrt(x) == math.isqrt(x)
    nums = rng.sample(range(50), rng.randint(1, 12))     # distinct, so neighbours differ
    i = find_peak(nums)
    padded = [-math.inf] + nums + [-math.inf]
    assert padded[i] < padded[i + 1] > padded[i + 2]
    ivs = [[s, s + rng.randint(1, 6)] for s in (rng.randint(0, 12) for _ in range(rng.randint(0, 7)))]
    assert min_removals(ivs) == brute_removals(ivs)

print(stock_spans([100, 80, 60, 70, 60, 75, 85]))       # [1, 1, 1, 2, 1, 4, 6]
print(isqrt(30), isqrt(10**30 + 1))                     # 5 1000000000000000
print(find_peak([1, 3, 2, 4, 1]))                       # 3 (index 1 is also a peak)
print(sorted(top_k_frequent([1, 1, 1, 2, 2, 3, 4, 4, 4, 4], 2)))   # [1, 4]
print(min_removals([[1, 3], [2, 4], [3, 5], [0, 7], [5, 8], [6, 9], [8, 10]]))  # 3
print("2000 random tests passed")

Two details. isqrt uses exact integers: int(math.sqrt(x)) goes through a float and is wrong for large x (for $x = (10^8 + 1)^2 - 1$ it returns $10^8 + 1$). And find_peak returns index 3, not the first peak at index 1: its predicate is not monotone, so binary search finds a switch point.

6. Where it shows up #

• Autodiff and parsers. Reverse-mode autodiff records the forward operations on a tape and runs the backward pass in reverse order: last in, first out. Expression parsers and tokenizers that handle nested brackets use a stack.
• Signals. A running maximum over a window (a 1-D max pool, the envelope of a seismogram) costs $O(n)$ with a monotonic deque, for any window length. The largest all-ones rectangle in a binary mask (for example, a cloud-free block of a satellite image) runs the histogram algorithm on every row.
• Binary search in ML code. np.searchsorted and torch.searchsorted put values into sorted bins. Sampling from a categorical distribution is a cumulative sum plus a search for the first cumulative probability $\ge u$, with $u$ uniform in $[0, 1)$. On the answer: the largest batch size that fits in GPU memory, and git bisect to find the commit that broke a training run.
• Top-$k$ and merging. Beam search keeps the $B$ best partial sequences at each step. CPU vector search libraries keep a size-$k$ heap of the best distances per query. Top-$k$ sampling in LLM decoding is the same selection problem, done on the GPU with torch.topk. Merging sorted shards uses a heap with one entry per shard.
• Intervals in science and systems. Merging overlapping time windows of sensor records, finding gaps in a data archive, merging genome annotations, and counting the GPUs in use over time from job start and end events are all "sort, then sweep".
• Greedy in ML. Huffman coding is greedy with an exchange-argument proof (Information theory, lesson 05). BPE tokenization greedily merges the most frequent pair; it is a heuristic, not an optimal compressor. Greedy decoding is an unsafe greedy: the most likely next token does not always lead to the most likely sequence.

7. Common mistakes #

• Popping an empty stack. At a closing bracket, check that the stack is not empty; at the end, check that it is empty.
• Values instead of indices on a monotonic stack. You usually need a distance or a width, so store indices.
• Strict or not strict. Is 73 "warmer" than 73? The pop condition (< or <=) decides it; say it aloud.
• Two range styles in one loop. while lo <= hi with hi = n - 1 (closed) and while lo < hi with hi = n (half-open) need different updates. Keep one style.
• An update that does not shrink the range: lo = mid with mid = (lo + hi) // 2 loops forever when $hi = lo + 1$.
• A predicate that is not monotone, or a search range that does not contain the answer.
• Floats in integer problems: math.ceil(p / k) and int(math.sqrt(x)) fail for large integers; use (p + k - 1) // k and integer comparisons.
• Wrong heap direction. A max-heap of all $n$ items for "the $k$ largest" needs $O(n)$ memory. Use a min-heap of size $k$.
• Reading the heap as sorted. Only heap[0] has a fixed meaning; heap[-1] is not the maximum.
• Comparing payloads on ties (TypeError), or forgetting the sign when you negate keys.
• Intervals: last_end = e instead of max(last_end, e) when merging; mixing the closed and half-open conventions; sorting by the wrong key.
• Greedy without proof. Passing the examples is not a proof. Test against a brute force, then give the exchange argument.

8. Check yourself #

1. Next greater element with the stack, on a strictly increasing list of $n$ values: how many pushes and pops, and how large does the stack get? And on a strictly decreasing list?
   Answer

   Increasing: $n$ pushes, $n - 1$ pops (each value pops the previous one), at most 1 index on the stack. Decreasing: $n$ pushes, 0 pops, the stack grows to $n$. Both are $O(n)$.
2. a = [1, 2, 2, 2, 5]. Give bisect_left(a, 2), bisect_right(a, 2), the number of 2s, and the same for the value 3.
   Answer

   1 and 4, so three 2s. For 3: both are 4 (the insertion position), so zero 3s.
3. Packages of weights $1, 2, \dots, 10$ must be shipped in order within 5 days; each day takes the next packages in the line, with total weight at most the capacity $c$. Which range do you search for the smallest $c$, why is the predicate monotone, and what is the answer?
   Answer

   $c \in [10, 55]$: below 10 the heaviest package never fits, and $c = 55$ (the total) always works in 1 day. If $c$ works, $c + 1$ works with the same loading, so "$c$ is enough" is monotone. Binary search, with greedy loading as the test, gives 15 (days: 1–5, 6–7, 8, 9, 10).
4. Where is the maximum of a min-heap, and what does it cost to find it?
   Answer

   In a leaf, one of the indices $\lfloor n/2 \rfloor, \dots, n-1$, because an internal node is never larger than its children. Finding it costs $O(n)$: a scan over about $n/2$ leaves.
5. Numbers arrive one by one. After each number you must report the $k$-th largest so far. What do you store, and what does one update cost?
   Answer

   A min-heap of the $k$ largest numbers so far; the answer is heap[0]. One update is a comparison with the root and at most one heapreplace: $O(\log k)$.
6. Why is "sort by start" right for merging, but "sort by end" right for scheduling?
   Answer

   Merging needs "once the next start is past the block's end, the block is final", which holds when later intervals start later. Scheduling needs "the first choice leaves the most room for the rest", which is the earliest end; the exchange argument proves it.

9. Interview angle #

Recognize the pattern from the wording.

What to say before you code. Monotonic stack: what it holds, why it is ordered, and the push-once, pop-once bound. Binary search: the predicate, the range $[lo, hi)$, the invariant, and why the range shrinks. Heap: the direction and the size. Greedy: the rule and the exchange argument in three sentences.

Typical questions and short model answers.

1. "Why is your Daily Temperatures solution $O(n)$?" — "Each day is pushed onto the stack exactly once and popped at most once. The inner loop pops, so over the whole run it runs at most $n$ times in total. Every comparison either pops a day or ends the inner loop, so there are at most $2n$ comparisons. The extra space is the stack, $O(n)$ in the worst case, for falling temperatures."
2. "Find the minimum eating speed so that all piles are eaten in $h$ hours." — "If speed $k$ is enough, any faster speed is also enough, so the predicate is monotone. I search $k$ in $[1, \max p]$ with the half-open template; the test sums $\lceil p/k \rceil$ with integer arithmetic, $(p + k - 1) // k$. That is $O(n \log \max p)$."
3. "The 10 largest of a huge stream?" — "A min-heap of size 10. The root is the smallest of the current top 10, so each new item is compared with the root and replaces it if larger. $O(n \log k)$ time and $O(k)$ memory. Sorting would need all the data in memory and $O(n \log n)$. If all data fits in memory and I need only the $k$-th value, quickselect is $O(n)$ on average."
4. "Why is heapify linear?" — "It sifts down from the bottom. Half of the nodes are leaves and do not move, a quarter move at most one level, and so on. The sum $\sum_h h\,n/2^{h+1}$ is $n$, so the total is $O(n)$. Pushing $n$ items one by one is $O(n \log n)$ in the worst case."
5. "Maximum number of non-overlapping meetings — why is your greedy correct?" — "I sort by end and take every meeting that starts after the last one I took. Exchange argument: take any optimal schedule and its first-ending meeting. My first choice ends no later, so I can swap it in, and the schedule stays valid with the same size. Then the same argument applies to the rest. Earliest start fails on one long meeting that covers two short ones."

Typical follow-ups. "Values can repeat?" (monotonic stack: strict or not strict; rotated search: the worst case becomes $O(n)$). "A stream?" (the monotonic stack and the size-$k$ heap work online). "$P$ is expensive?" (binary search calls it only $O(\log \text{range})$ times). "Intervals arrive sorted?" (one $O(n)$ pass, as in Insert Interval). "Median of a stream?" (two heaps).

10. Practice #

The notebook for this lesson runs in Colab. Try each exercise from memory first. Each one is tested against a brute force or the standard library on random inputs:

1. daily_temperatures: a monotonic stack.
2. lower_bound: the half-open binary search, compared with bisect.bisect_left.
3. min_eating_speed: binary search on the answer (Koko Eating Bananas).
4. kth_largest with a size-$k$ heap, and merge_intervals.
5. max_non_overlapping: the earliest-end greedy, checked against all subsets of small inputs.

Timed practice (25 minutes each, talking aloud): Valid Parentheses, Evaluate Reverse Polish Notation, Daily Temperatures, Search in Rotated Sorted Array, Koko Eating Bananas, Kth Largest Element in an Array, Merge Intervals, Non-overlapping Intervals, Meeting Rooms II, Gas Station; harder: Largest Rectangle in Histogram, Find Median from Data Stream.

Say it aloud drill. Without code, explain in 90 seconds why lo = mid + 1 is safe and lo = mid is not, then explain the exchange argument for interval scheduling. Record yourself and check that you said the invariant both times.

11. Watch and read #

• Jeff Erickson, Algorithms (free PDF), chapter 4, Greedy Algorithms: §4.2 (earliest finish first, with the exchange argument) and §4.3 (the general pattern). The whole book is on the author's page.
• Kleinberg and Tardos, Algorithm Design, chapter 4, in the lecture slides by Kevin Wayne: interval scheduling, interval partitioning (meeting rooms) and "greedy stays ahead".
• Sedgewick and Wayne, Algorithms, 4th edition, §2.4 Priority Queues: swim (sift up), sink (sift down) and heapsort.
• cp-algorithms, Binary search: lower and upper bound, search on an arbitrary predicate, and continuous search.
• Python documentation: bisect (the exact meaning of bisect_left and bisect_right) and heapq (heapreplace versus heappushpop, and the priority-queue notes).
• Tech Interview Handbook cheatsheets for stacks, heaps and intervals; public problem lists Grind 75 and NeetCode 150 (sections Stack, Binary Search, Heap / Priority Queue, Intervals, Greedy).