Dijkstra, BFS, DFS, Sliding Window, Two Heaps & Monotonic Stack

Dijkstra's Algorithm — Shortest Path with Non-Negative Weights

Dijkstra's algorithm finds the shortest path from a single source node to every other node in a graph where every edge has a non-negative weight. It's the weighted generalization of BFS: BFS's "expand one layer at a time" guarantee only produces a shortest path because every edge implicitly costs the same (1 hop). The moment edges have different weights, that guarantee collapses — a path with more hops can still have a smaller total weight than a path with fewer hops, so a FIFO queue that only tracks hop count can no longer tell which path is actually shortest.

Dijkstra fixes this by replacing the FIFO queue with a min-heap keyed on the running total distance, and always expanding the currently-closest unvisited node next — a greedy choice. That greedy choice is provably correct as long as all weights are non-negative: once a node is popped as the closest remaining node, no path through any other, farther node could ever reach it more cheaply, because adding more non-negative edges to a path can only keep its total the same or make it larger, never smaller. Negative weights break that argument outright — a node already finalized as "closest so far" could later be beaten by a path that dips through a negative edge discovered afterward, so a finalized distance is no longer guaranteed final. Graphs with negative weights need Bellman-Ford instead, which relaxes every edge repeatedly rather than trusting a single greedy pop.

Worked Example: Shortest Driving Distance Between Six Towns

Six towns connected by two-way roads, each edge labeled with its driving distance in miles: Springfield-Riverton (4), Springfield-Oakdale (2), Riverton-Oakdale (1), Riverton-Millbrook (5), Oakdale-Millbrook (8), Oakdale-Fairview (10), Millbrook-Fairview (2), Millbrook-Hartwell (6), Fairview-Hartwell (3). Starting from Springfield, what's the shortest driving distance to every other town?

Full Trace

Final shortest distances from Springfield: Oakdale 2, Riverton 3, Millbrook 8, Fairview 10, Hartwell 13. Notice Riverton's tentative distance is updated twice — first to 4 via the direct Springfield-Riverton edge, then down to 3 once Oakdale is finalized and the cheaper Oakdale-Riverton edge (distance 1) is found. The heap now holds a stale (4, Riverton) entry alongside the fresh (3, Riverton) one; when that stale entry is eventually popped, its distance (4) no longer matches Riverton's current best-known distance (3), so it's discarded as a no-op rather than re-processed. The same thing happens later with stale entries for Millbrook, Fairview, and Hartwell — this run popped 10 times total but only finalized 6 nodes, the other 4 pops all being stale skips.

Code

import heapq

def dijkstra(graph, start):
    # every node starts unreached except the source itself
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    # heap entries are (distance, node); source starts at distance 0
    heap = [(0, start)]
    while heap:
        current_dist, node = heapq.heappop(heap)
        # lazy deletion -- heapq has no decrease-key, so a node can sit
        # in the heap multiple times; skip stale entries here instead
        if current_dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            # relax the edge only if this path is strictly better
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return distances

Complexity

O((V + E) log V) with a binary heap — each edge can push at most one stale/duplicate entry onto the heap, and every push/pop costs O(log V). O(V²) with a simple array-based version that scans for the minimum unvisited distance instead of using a heap — worse for sparse graphs, but actually faster in practice for dense graphs where E is close to V², since it avoids the log V heap overhead entirely.

Key Functions & Tricks

• heapq.heappush / heapq.heappop — the priority queue that always hands back the currently-closest unvisited node.
• Lazy deletion: if current_dist > distances[node]: continue — Python's heapq has no decrease-key, so skip stale entries instead of trying to update them in place.
• float("inf") — initial tentative distance for every node before it's reached.
• Early exit on popping the destination — if only one target's shortest distance is needed (not all of them), return the moment that node is popped instead of draining the whole heap.

Examples in This Set

#50 (min-latency service path) already implements this exact algorithm for a Fin-flavored service-routing scenario.

BFS — Breadth-First Search

BFS explores a graph (or implicit graph, like a grid) one "layer" at a time — visit everything one hop from the start, then everything two hops away, then three, and so on — by pushing neighbors onto the back of a queue and always popping from the front. That strict first-in-first-out order is the entire mechanism: it guarantees every node at distance d is dequeued before any node at distance d + 1 is ever dequeued, which is exactly why the first time BFS reaches a node is guaranteed to be via a shortest path in an unweighted graph. Nothing about BFS "knows" about shortest paths directly — the shortest-path guarantee falls straight out of the FIFO queue discipline.

Reach for BFS the moment a problem asks for "shortest," "fewest," or "minimum number of steps/hops" in a graph where every edge costs the same — a friend network, an unweighted grid, a word-transformation ladder. If edges have different weights, BFS's guarantee breaks and you need Dijkstra instead.

Worked Example: Shortest Hop Count in a Friend Network

Six people, each an undirected edge meaning "these two are friends": amy-bob, amy-cara, bob-dan, cara-eve, dan-eve, dan-finn, eve-finn. Question: what's the fewest introductions needed to connect amy to finn?

from collections import deque

graph = {
    "amy": ["bob", "cara"],
    "bob": ["amy", "dan"],
    "cara": ["amy", "eve"],
    "dan": ["bob", "eve", "finn"],
    "eve": ["cara", "dan", "finn"],
    "finn": ["dan", "eve"],
}

def bfs_shortest_path(graph, start, goal):
    # mark visited at PUSH time, not pop time -- see Pitfalls
    visited = {start}
    queue = deque([(start, [start])])
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

Full Trace

Final path: amy → bob → dan → finn, hop count 3. Note eve was also reachable in 2 hops (via cara) but her neighbors dan and finn were already visited by the time she's popped, so she contributes nothing new — the queue naturally prunes redundant paths.

Complexity

O(V + E) time — every vertex is enqueued once and every edge is examined once. O(V) space for the visited set and queue.

Examples in This Set

#10 (shortest escalation path), #24 (clone graph — BFS/DFS traversal to visit every node), #36 (count duplicate ticket clusters — flood fill), #42 (shortest query reformulation — word-ladder-style BFS).

DFS — Depth-First Search

DFS explores as far as possible down one branch before backtracking — pick a neighbor, recurse into it fully (or push it onto an explicit stack), and only return to try a sibling once that entire subtree is exhausted. Where BFS's queue enforces "closest first," DFS's stack (whether the literal call stack via recursion, or an explicit list used as a stack) enforces "deepest-first, unwind on failure." That makes DFS the natural fit whenever the question isn't about distance at all but about reachability or exhaustive exploration: is everything connected, does a path exist satisfying some constraint, how many separate groups are there.

Reach for DFS for "visit everything reachable," "count connected components/regions," "does a path exist," or backtracking-style search where you need to try a choice, recurse, and undo it if it doesn't pan out. DFS gives no shortest-path guarantee — it just guarantees full coverage of whatever is reachable from the start.

Worked Example: Counting Islands in a Grid

A 4×5 grid of land (1) and water (0). Two land cells belong to the same island if they're adjacent up/down/left/right. How many separate islands are there?

grid = [
    [1, 1, 0, 0, 0],
    [1, 0, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 1],
]

rows, cols = len(grid), len(grid[0])

def count_islands(grid):
    visited = set()
    islands = 0

    def dfs(r, c):
        visited.add((r, c))
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 1 and (nr, nc) not in visited:
                    dfs(nr, nc)

    for r in range(rows):
        for c in range(cols):
            # unvisited land cell -- root of a brand-new island
            if grid[r][c] == 1 and (r, c) not in visited:
                islands += 1
                dfs(r, c)

    return islands

Full Trace

Total islands: 3. The scan hits (0,0) first and DFS immediately claims (1,0) and (0,1) as part of the same island before the outer loop ever reaches them on its own.

Complexity

O(V + E) — or O(rows × cols) for a grid, since each cell is visited once and each has a constant number of neighbors. O(V) space for the visited set plus recursion depth up to the size of the largest island.

Examples in This Set

#24 (clone escalation graph), #25 (word search — backtracking DFS over a grid), #36 (count duplicate ticket clusters — this exact island-counting shape).

Sliding Window

A sliding window turns an O(n²) "check every contiguous subarray/substring" brute force into O(n) by never re-scanning a range from scratch. Two pointers, left and right, define the current window; right only ever moves forward, expanding the window one element at a time while updating some running state incrementally (a running sum, a character-count map, a last-seen-index map). left only moves forward too, and only when the window currently violates whatever constraint the problem imposes — shrinking from the left until the constraint holds again. Because both pointers move strictly forward and neither ever resets backward, each one traverses the array at most once across the whole run, which is what gives the O(n) bound despite there being O(n²) possible windows in total.

Reach for this the moment a problem is about a contiguous range with some constraint that depends only on what's currently inside the window — "longest substring with at most K distinct characters," "smallest subarray summing to at least S," "window of size K." If the elements you need don't have to be contiguous, this pattern doesn't apply.

Worked Example: Longest Substring Without Repeating Characters

Given "abcabcbfb", find the length of the longest contiguous substring with no repeated characters.

def longest_unique_substring(s):
    # maps each character to the index it was last seen at
    last_seen = {}
    left = 0
    best_len = 0
    for right, ch in enumerate(s):
        # only shrink past a repeat if it's INSIDE the current window
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        window_len = right - left + 1
        best_len = max(best_len, window_len)
    return best_len

Full Trace

Input: "abcabcbfb"

Final answer: 3 (e.g. "abc"). Note at right=6 the earlier b from right=1 is stale — it's outside the current window (left is already at 3) — so the code's last_seen[ch] >= left check correctly ignores it and only jumps left past the repeat at right=4.

Complexity

O(n) time — each pointer visits each index at most once. O(min(n, alphabet size)) space for the last-seen map.

Examples in This Set

#15 (sliding window maximum), #22 (longest unique topic run — this exact pattern), #44 (sliding window minimum response time).

Two Heaps

The two-heaps pattern maintains a running median (or any "split the data in half" statistic) over a stream by keeping two heaps: a max-heap holding the smaller half of the numbers seen so far, and a min-heap holding the larger half. Python's heapq is min-heap only, so the max-heap side is emulated by pushing negated values. The median is then always sitting at the top of one or both heaps — O(log n) to insert, O(1) to read the median — instead of O(n log n) to re-sort the whole stream every time a new number arrives.

The mechanism that makes this work is a strict size invariant, rebalanced after every single insertion: len(max_heap) - len(min_heap) must stay in {0, 1}. Insert into whichever heap is the correct side for the new value (compare against the max-heap's top), then immediately move one element across if the sizes drift out of balance. Skip the rebalance step even once and both the size invariant and the median answer silently go wrong.

Worked Example: Running Median of a Latency Stream

Stream of latency readings arriving one at a time: 5, 15, 1, 3, 8, 7, 9, 2. After each new reading, report the median of everything seen so far.

import heapq

def running_median(stream):
    small = []  # max-heap of the lower half, values stored negated
    large = []  # min-heap of the upper half
    medians = []
    for num in stream:
        # route the new value to the correct half
        if not small or num <= -small[0]:
            heapq.heappush(small, -num)
        else:
            heapq.heappush(large, num)

        # rebalance: small may lead large by at most 1
        if len(small) > len(large) + 1:
            val = -heapq.heappop(small)
            heapq.heappush(large, val)
        elif len(large) > len(small):
            val = heapq.heappop(large)
            heapq.heappush(small, -val)

        if len(small) > len(large):
            median = -small[0]
        else:
            median = (-small[0] + large[0]) / 2
        medians.append(median)
    return medians

Full Trace

Heap contents above are shown sorted descending/ascending for readability — the actual heap arrays aren't fully sorted internally, only the top element (heap[0]) is guaranteed correct. After inserting 3, notice the size invariant forced a rebalance: 5 moved from the max-heap into the min-heap so the sizes stay within 1 of each other (2 and 2), which is exactly why the median after inserting 3 is (3 + 5) / 2 = 4.0 rather than something computed from an unbalanced split.

Complexity

O(log n) per insert (one heap push, plus at most one rebalance push/pop), O(1) to read the current median. O(n) total space.

Examples in This Set

#16 (running median of latency) — the only problem in this set that uses literal two-heaps; it's a narrower pattern than the general heap/top-k family covered on the Pattern Catalog.

Monotonic Stack

A monotonic stack keeps its elements in strictly increasing or strictly decreasing order at all times, enforced by popping violators before every push. The payoff: for problems asking "what's the next element to the right that's greater/smaller than me," a monotonic stack answers it for every element in a single O(n) left-to-right pass instead of an O(n²) pair of nested loops. The mechanism is that whenever a new element arrives and it breaks the stack's monotonic order (say the stack is decreasing and the new value is larger than the top), every element it just invalidated has, by definition, just found its "next greater" — so pop each of them off and record the answer, then push the new element.

Reach for this on "next greater/smaller element," "days until a warmer temperature," or "the width of the largest rectangle in a histogram" — anywhere the question is about the nearest element satisfying an ordering comparison, scanned once. It's closely related to but distinct from a monotonic deque (used for sliding-window maximum/minimum, see #15/#44 above): a monotonic stack only ever pops from one end and answers "next greater to the right," while a monotonic deque pops from both ends to also evict elements that have aged out of a fixed-size window — same ordering discipline, different problem shape.

Worked Example: Days Until a Warmer Temperature

Given daily temperatures [73, 74, 75, 71, 69, 72, 76, 73], for each day output how many days until a strictly warmer day (0 if none exists).

def days_until_warmer(temps):
    n = len(temps)
    answer = [0] * n
    # stack holds indices; temps at these indices are strictly
    # decreasing from bottom to top
    stack = []
    for i, t in enumerate(temps):
        # today is warmer than the top of the stack -- resolve it
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

Full Trace

Input: [73, 74, 75, 71, 69, 72, 76, 73] (indices 0-7)

Final answer: [1, 1, 4, 2, 1, 1, 0, 0]. Days 6 and 7 (temps 76 and 73) are left at 0 since nothing warmer ever arrives after them — they stay on the stack forever and never get resolved, which is exactly why the answer array is pre-initialized to 0 rather than left unset.

Complexity

O(n) time — every index is pushed exactly once and popped at most once, even though the pattern is nested inside a while loop. O(n) space for the stack in the worst case (strictly decreasing input).

Examples in This Set

No direct example in this set. The 50 problems here have monotonic-deque problems (#15, #44) but none use a literal monotonic stack for a next-greater-style query — a genuine gap rather than a mislabeled link, same honesty pattern as Bit Manipulation on the Pattern Catalog.

Common Pitfalls Across All Six