🕸️ Graph

The night-before sheet: spot the pattern, write the simple version, say the right thing out loud.

💭 Your own rules: DSA thoughts → Graph, Must Remember. Each section below links the ones that apply.

🧠 0 · How to think

"Things and connections. If you can say “X connects to Y”, it's a graph, even when the word graph never appears."

There are only two ways to walk a graph, and every algorithm below is one of them with a twist:

🧭 1 · Spot it

Is it secretly a graph? If you can name the nodes and the edges, yes.

The emoji is the hook: remember the picture, and the tool comes with it. The same emojis come back in each section's 🧩 idea box.

🔒 = LeetCode Premium. For 261, 269, 305, 323, 444 and 505 the tracker links a free LintCode or NeetCode copy; for 1168 it links CSES 1675 Road Reparation (same Kruskal core).

🧱 2 · Setup

Use an adjacency list: graph[u] = the neighbours of u. It takes O(V + E) space. Use a matrix only when you need an O(1) "is there an edge?" check on a small, dense graph.

// Paste inside each grid function
const DIRS = [[-1, 0], [0, 1], [1, 0], [0, -1]]; // up, right, down, left

// Edge list → adjacency list. Create every node first so isolated nodes exist.
const graph: number[][] = Array.from({length: n}, () => []);

for(const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u); // undirected = add both ways; directed = drop this line
}
// Weighted: graph[u].push([v, w])

A heap for Dijkstra and Kruskal

JavaScript has no built-in heap. On LeetCode use the built-in MinPriorityQueue (that's what your solutions call). An interview doc has none, so be able to type the class below in 3 minutes: it has the same API, so your Dijkstra code runs unchanged.

// On LeetCode (built in)
const pq = new MinPriorityQueue<number[]>(x => x[0]); // ordered by x[0]
pq.enqueue([0, src]);
const [d, node] = pq.dequeue();
while(!pq.isEmpty()) { /* ... */ }

// Interview doc (no built-in): same API as above
class MinPriorityQueue<T> {
    private items: T[] = [];
    constructor(private key: (x: T) => number) {}

    isEmpty(): boolean { return this.items.length === 0; }

    enqueue(item: T): void {
        const a = this.items;
        a.push(item);
        let i = a.length - 1;

        while(i > 0) { // bubble up while smaller than the parent
            const parent = Math.floor((i - 1) / 2);
            if(this.key(a[parent]) <= this.key(a[i])) break;
            [a[parent], a[i]] = [a[i], a[parent]];
            i = parent;
        }
    }

    dequeue(): T {
        const a = this.items;
        const top = a[0];
        const last = a.pop()!;

        if(a.length > 0) {
            a[0] = last; // move the last item to the root, then sink it
            let i = 0;

            while(true) {
                const left = 2 * i + 1;
                const right = 2 * i + 2;
                let smallest = i;

                if(left < a.length && this.key(a[left]) < this.key(a[smallest])) smallest = left;
                if(right < a.length && this.key(a[right]) < this.key(a[smallest])) smallest = right;
                if(smallest === i) break;

                [a[smallest], a[i]] = [a[i], a[smallest]];
                i = smallest;
            }
        }

        return top;
    }
}

🌊 3 · BFS: fewest steps

"Explore in rings. The first time you reach a node is the shortest way there."

Only true when every edge costs the same. Process the graph one level at a time: keep one queue array and a front index. At the start of each level take size = queue.length - front and process exactly that many. The level number is the distance. This avoids queue.shift(), which is O(n).

// 🍊 ROTTING ORANGES (multi-source BFS)
function orangesRotting(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;

    let fresh = 0;
    let queue: number[][] = [];

    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === 1) fresh++;
            else if(grid[i][j] === 2) queue.push([i, j]); // ALL sources start together
        }
    }

    if(fresh === 0) return 0;
    if(queue.length === 0) return -1;

    let front = 0;
    let time = -1; // the first pass is the starting level, so it brings time to 0

    const DIRS = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    let visitedFresh = 0;

    while(front < queue.length) {
        let size = queue.length - front; // this level only
        time++;

        while(size--) {
            const [row, col] = queue[front++];

            for(const [dr, dc] of DIRS) {
                const nr = dr + row;
                const nc = dc + col;

                if(nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    if(grid[nr][nc] === 1) {
                        grid[nr][nc] = 2; // mark when ADDED, not when popped
                        visitedFresh++;
                        queue.push([nr, nc]);
                    }
                }
            }
        }
    }

    return visitedFresh === fresh ? time : -1;
};

time = -1 is safe only because the two early returns run first: with no fresh oranges, or no rotten ones, the loop would give the wrong answer.

Implicit graph: generate the neighbours

// 🪜 WORD LADDER (front/back bidirectional BFS)
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    if(beginWord === endWord) return 0;
    const wordSet = new Set(wordList);

    if(!wordSet.has(endWord)) return 0;

    let front = new Set<string>([beginWord]);
    let back = new Set<string>([endWord]);
    let level = 1; // counts words, not edges

    while(front.size > 0) {
        if(front.size > back.size) {
            [front, back] = [back, front]; // always expand the smaller side
        }

        const nextLevel = new Set<string>();
        level++;

        for(const word of front) {
            for(let i = 0; i < word.length; i++) {
                const originCh = word[i];

                for(let c = 0; c < 26; c++) {
                    const newCh = String.fromCharCode(c + 97);

                    if(newCh === originCh) continue;

                    const newWord = word.slice(0, i) + newCh + word.slice(i + 1);

                    if(back.has(newWord)) return level; // the two sides met

                    if(wordSet.has(newWord)) {
                        wordSet.delete(newWord); // delete = mark visited
                        nextLevel.add(newWord);
                    }
                }
            }
        }

        front = nextLevel;
    }

    return 0;
};

🌀 4 · DFS: islands, copies, cycles

"Go as deep as you can, then back up."

Use it for anything about structure: components, copying, cycles, colouring, and searching all paths. Recursion is the cleanest; switch to an explicit stack only if depth can pass about 10,000.

// 🏝️ NUMBER OF ISLANDS (DFS flood fill)
function numIslands(grid: string[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    let isLands = 0;

    const DIRS = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    function dfs(row: number, col: number): void {
        grid[row][col] = '0'; // mark visited in place

        for(const [dr, dc] of DIRS) {
            const nr = dr + row;
            const nc = dc + col;

            if(nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
                dfs(nr, nc);
            }
        }
    }

    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === '1') {
                isLands++; // new island found
                dfs(i, j);
            }
        }
    }

    return isLands;
};

You check bounds and '1' before recursing, so dfs marks on entry and needs no early-return line.

The grid family

Clone a graph

// 🧬 CLONE GRAPH (DFS + map)
function cloneGraph(node: _Node | null): _Node | null {
    if(!node) return node;

    const cloned = new Map<_Node, _Node>(); // old node → copy; also the visited set

    function dfs(original: _Node): _Node {
        if(cloned.has(original)) return cloned.get(original)!;

        const copy = new _Node(original.val);
        cloned.set(original, copy); // save BEFORE recursing (cycles!)

        for(const nei of original.neighbors) {
            copy.neighbors.push(dfs(nei));
        }

        return copy;
    }

    return dfs(node);
};

Cycle in a directed graph

// 🔁 DIRECTED CYCLE (3-state DFS)
function hasCycle(n: number, graph: number[][]): boolean {
    // 0 = not visited, 1 = on the current path, 2 = fully explored
    const state: number[] = new Array(n).fill(0);

    function dfs(node: number): boolean { // true = no cycle through this node
        state[node] = 1;

        for(const next of graph[node]) {
            if(state[next] === 1) return false; // back to our own path = cycle
            if(state[next] === 0 && !dfs(next)) return false;
        }

        state[node] = 2;
        return true;
    }

    for(let i = 0; i < n; i++) {
        if(state[i] === 0 && !dfs(i)) return true;
    }

    return false;
}

Undirected cycle: use Union-Find (§6): an edge whose two ends are already connected closes a cycle. 261 Valid Tree🔒: exactly n − 1 edges and everything connected.

Two groups: bipartite

// 🎨 IS GRAPH BIPARTITE (DFS and BFS colouring)
function isBipartite(graph: number[][]): boolean {
    const n = graph.length;

    const color = Array(n).fill(-1); // -1 = not painted

    function dfs(node: number, col: number): boolean {
        color[node] = col;

        for(const nei of graph[node]) {
            if(color[nei] === -1) {
                if(!dfs(nei, 1 - col)) return false;
            } else if(color[nei] === col) return false; // same colour on both ends
        }

        return true;
    }

    function bfs(node: number, col: number): boolean {
        color[node] = col;
        const queue = [node];
        let front = 0;

        while(front < queue.length) {
            const curr = queue[front++];

            for(const nei of graph[curr]) {
                if(color[nei] === -1) {
                    color[nei] = 1 - color[curr];
                    queue.push(nei);
                } else if(color[nei] === color[curr]) return false;
            }
        }

        return true;
    }

    for(let i = 0; i < n; i++) { // graph may be disconnected
        if(color[i] === -1) {
            // if(!dfs(i, 0)) return false;
            if(!bfs(i, 0)) return false;
        }
    }

    return true;
};

Your accepted submission uses bfs; dfs is the same check with recursion. 886 Possible Bipartition is the same code after building the graph from the "dislikes" pairs. A graph is bipartite exactly when it has no odd-length cycle.

Weighted BFS: Evaluate Division

// ➗ EVALUATE DIVISION (graph + BFS, carry the product)
// a/b = 2 means edge a→b (2) and b→a (1/2).
function calcEquation(eq: string[][], vals: number[], que: string[][]): number[] {
    const graph = new Map<string, [string, number][]>();
    const eLen = eq.length;

    for(let i = 0; i < eLen; i++) {
        const [u, v] = eq[i];
        const val = vals[i];

        if(!graph.has(u)) graph.set(u, []);
        if(!graph.has(v)) graph.set(v, []);

        graph.get(u)!.push([v, val]);
        graph.get(v)!.push([u, 1 / val]);
    }

    function bfs(source: string, target: string): number {
        const visited = new Set<string>();
        visited.add(source);

        const queue: [string, number][] = [[source, 1]];
        let front = 0;

        while(front < queue.length) {
            const [node, currProd] = queue[front++];

            if(node === target) return currProd;

            for(const [nei, neiVal] of graph.get(node) ?? []) {
                if(!visited.has(nei)) {
                    const newProd = neiVal * currProd;
                    visited.add(nei);
                    queue.push([nei, newProd]);
                }
            }
        }

        return -1;
    }

    const qLen = que.length;
    const ans: number[] = [];

    for(let i = 0; i < qLen; i++) {
        const [u, v] = que[i];

        if(!graph.has(u) || !graph.has(v)) ans.push(-1);
        else if(u === v) ans.push(1);
        else ans.push(bfs(u, v));
    }

    return ans;
};

📊 5 · Topological sort: order with prerequisites

"Repeatedly take a task that nothing is waiting on."

Count each node's incoming edges (indegree). Start with every node at 0. Taking a node lowers its neighbours' counts, and any that reach 0 join the queue. If you finish with fewer than n nodes, the rest are stuck in a cycle. That one check also answers 207 "can you finish?"

// 📚 COURSE SCHEDULE II (Kahn's BFS topological sort)
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const adj: number[][] = Array.from({ length: numCourses }, () => []);
    const indegree: number[] = new Array(numCourses).fill(0);

    for (const [course, prereq] of prerequisites) {
        adj[prereq].push(course); // taking prereq unlocks course
        indegree[course]++;       // course has one more prerequisite to satisfy
    }

    const queue: number[] = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    let front = 0;
    let order = [];

    while (front < queue.length) {
        const course = queue[front++];
        order.push(course);

        for (const next of adj[course]) {
            indegree[next]--;
            if (indegree[next] === 0) queue.push(next);
        }
    }

    return order.length === numCourses ? order : []; // stuck before n → cycle
};

Same answer with DFS (your accepted submission): post-order, then reverse.

// DFS version: post-order, then reverse
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const adj: number[][] = Array.from({ length: numCourses }, () => []);
    for (const [course, prereq] of prerequisites) {
        adj[prereq].push(course);
    }

    let order = [];

    // 0 = not visited, 1 = on the active path, 2 = fully explored
    const state: number[] = new Array(numCourses).fill(0);

    function dfs(node: number): boolean {
        state[node] = 1;

        for (const next of adj[node]) {
            if (state[next] === 1) return false;
            if (state[next] === 0 && !dfs(next)) return false;
        }

        state[node] = 2;
        order.push(node);
        return true;
    }

    for (let i = 0; i < numCourses; i++) {
        if (state[i] === 0 && !dfs(i)) return [];
    }

    return order.reverse();
};

Restyled to match 210, not copied from your code (your NeetCode solution wasn't readable).

// 👽 ALIEN DICTIONARY (Kahn's on letters)
function alienOrder(words: string[]): string {
    const adj = new Map<string, Set<string>>();
    const indegree = new Map<string, number>();

    for(const word of words) { // every letter is a node
        for(const ch of word) {
            if(!adj.has(ch)) adj.set(ch, new Set());
            if(!indegree.has(ch)) indegree.set(ch, 0);
        }
    }

    for(let i = 0; i < words.length - 1; i++) {
        const w1 = words[i];
        const w2 = words[i + 1];

        if(w1.length > w2.length && w1.startsWith(w2)) return ''; // "abc" before "ab" = invalid

        for(let j = 0; j < Math.min(w1.length, w2.length); j++) {
            if(w1[j] !== w2[j]) {
                if(!adj.get(w1[j])!.has(w2[j])) { // skip duplicate edges
                    adj.get(w1[j])!.add(w2[j]);
                    indegree.set(w2[j], indegree.get(w2[j])! + 1);
                }
                break; // only the FIRST difference counts
            }
        }
    }

    const queue: string[] = [];
    for(const [ch, deg] of indegree) {
        if(deg === 0) queue.push(ch);
    }

    let front = 0;
    let order = '';

    while(front < queue.length) {
        const ch = queue[front++];
        order += ch;

        for(const next of adj.get(ch)!) {
            indegree.set(next, indegree.get(next)! - 1);
            if(indegree.get(next) === 0) queue.push(next);
        }
    }

    return order.length === indegree.size ? order : ''; // stuck → cycle
};

🔗 6 · Union-Find: who is in which group

"Every group has a root. Two nodes are connected if they have the same root."

Best when edges arrive one at a time and you keep asking "connected yet?" With path compression and union by rank, each operation is nearly O(1). It works on undirected graphs only.

// 🔗 REDUNDANT CONNECTION (Union-Find, rank + path compression)
function findRedundantConnection(edges: number[][]): number[] {
    const n = edges.length;

    const parent = Array.from({length: n + 1}, (_, i) => i); // nodes are 1..n
    const rank = Array(n + 1).fill(0);
    // let count = n;  // for "count components": uncomment, and do count-- before return true

    function find(x: number): number {
        let root = x;

        while(parent[root] !== root) {
            root = parent[root];
        }

        while(parent[x] !== root) { // path compression
            const next = parent[x];
            parent[x] = root;
            x = next;
        }

        return root;
    }

    function union(x: number, y: number): boolean {
        const px = find(x);
        const py = find(y);

        if(px === py) return false; // already connected, this edge makes a cycle

        if(rank[px] < rank[py]) parent[px] = py;
        else if(rank[px] > rank[py]) parent[py] = px;
        else {
            parent[px] = py;
            rank[py]++;
        }

        return true;
    }

    for(const [u, v] of edges) {
        if(!union(u, v)) return [u, v];
    }

    return [];
};

// 📧 ACCOUNTS MERGE (Union-Find on emails)
function accountsMerge(accounts: string[][]): string[][] {
    const parent = new Map<string, string>();
    const rank = new Map<string, number>();
    const owner = new Map<string, string>(); // email -> account name

    function find(x: string): string {
        let root = x;

        while(parent.get(root) !== root) {
            root = parent.get(root)!;
        }

        while(parent.get(x) !== root) {
            const next = parent.get(x)!;
            parent.set(x, root);
            x = next;
        }

        return root;
    }

    function union(x: string, y: string): void {
        const px = find(x);
        const py = find(y);

        if(px === py) return;

        const rankX = rank.get(px)!;
        const rankY = rank.get(py)!;

        if(rankX < rankY) {
            parent.set(px, py);
        } else if(rankX > rankY) {
            parent.set(py, px);
        } else {
            parent.set(px, py);
            rank.set(py, rankY + 1); // bump the new ROOT (py), not px
        }
    }

    for(const [name, ...emails] of accounts) {
        for(const email of emails) {
            if(!parent.has(email)) {
                parent.set(email, email);
                rank.set(email, 0);
                owner.set(email, name);
            }

            union(emails[0], email); // join every email to the account's first one
        }
    }

    const groups = new Map<string, string[]>();
    for(const email of parent.keys()) {
        const root = find(email);
        if(!groups.has(root)) groups.set(root, []);
        groups.get(root)!.push(email);
    }

    const res: string[][] = [];

    for(const [root, emails] of groups) {
        emails.sort();
        res.push([owner.get(root)!, ...emails]);
    }

    return res;
};

🛣️ 7 · Weighted shortest path

"BFS, but always expand the cheapest node next."

Dijkstra works when every weight is ≥ 0. JS heaps can't lower a key in place, so push a new entry and skip stale ones when they pop. Time is O(E log E), which is the same as O(E log V) because E ≤ V².

// 📡 NETWORK DELAY TIME (Dijkstra)
function networkDelayTime(times: number[][], n: number, k: number): number {
    const graph: number[][][] = Array.from({length: n}, () => []);

    for(const [u, v, w] of times) {
        const nu = u - 1; // nodes are 1..n, graph is 0-indexed
        const nv = v - 1;
        graph[nu].push([nv, w]);
    }

    const pq = new MinPriorityQueue<number[]>(x => x[0]); // [distance, node]
    pq.enqueue([0, k - 1]);
    const dist = Array(n).fill(Number.MAX_SAFE_INTEGER);
    dist[k - 1] = 0;

    while(!pq.isEmpty()) {
        const [currDist, node] = pq.dequeue();

        if(currDist > dist[node]) continue; // stale: a shorter path already won

        for(const [nei, w] of graph[node]) {
            const nextDist = w + currDist;

            if(nextDist < dist[nei]) {
                dist[nei] = nextDist;
                pq.enqueue([nextDist, nei]);
            }
        }
    }

    let maxVal = 0;

    for(let i = 0; i < n; i++) {
        if(dist[i] === Number.MAX_SAFE_INTEGER) return -1;
        maxVal = Math.max(dist[i], maxVal);
    }

    return maxVal;
};

The variation interviewers love: cost is a max, not a sum

Not in your tracker, so this is built from your 2290 Minimum Obstacle Removal shape with Math.max swapped in.

// 🧗 PATH WITH MINIMUM EFFORT (grid Dijkstra, cost = largest step)
function minimumEffortPath(heights: number[][]): number {
    const m = heights.length;
    const n = heights[0].length;

    const dist = Array.from({length: m}, () => Array(n).fill(Number.MAX_SAFE_INTEGER));
    const pq = new MinPriorityQueue<number[]>(x => x[2]); // [row, col, effort]

    dist[0][0] = 0;
    pq.enqueue([0, 0, 0]);

    const DIRS = [[-1, 0], [0, 1], [1, 0], [0, -1]];

    while(!pq.isEmpty()) {
        const [row, col, d] = pq.dequeue();

        if(row === m - 1 && col === n - 1) return d; // first time target pops = answer

        if(d > dist[row][col]) continue;

        for(const [dr, dc] of DIRS) {
            const nr = row + dr;
            const nc = col + dc;

            if(nr >= 0 && nr < m && nc >= 0 && nc < n) {
                const newDist = Math.max(d, Math.abs(heights[nr][nc] - heights[row][col])); // ⭐ max, not +

                if(newDist < dist[nr][nc]) {
                    dist[nr][nc] = newDist;
                    pq.enqueue([nr, nc, newDist]);
                }
            }
        }
    }

    return 0;
};

At most K stops: Bellman-Ford

// ✈️ CHEAPEST FLIGHTS WITHIN K STOPS (Bellman-Ford, one round per flight)
function findCheapestPrice(n: number, edges: number[][], src: number, dst: number, k: number): number {
    let dist = Array(n).fill(Number.MAX_SAFE_INTEGER);
    dist[src] = 0;

    for(let f = 0; f < k + 1; f++) { // k stops = k + 1 flights
        const nextDist = [...dist];  // copy: read last round, write this one
        let changed = false;

        for(const [u, v, p] of edges) {
            if(dist[u] + p < nextDist[v]) {
                nextDist[v] = dist[u] + p;
                changed = true;
            }
        }

        dist = nextDist;

        if(!changed) break; // nothing improved: later rounds can't either
    }

    return dist[dst] === Number.MAX_SAFE_INTEGER ? -1 : dist[dst];
};

Number.MAX_SAFE_INTEGER + p is never smaller than a real cost, so the unreached check stays safe. Don't switch to Infinity without re-checking the comparisons.

All pairs (1334, n ≤ 100): Floyd-Warshall, three loops with k outermost: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). O(V³) time, O(V²) space.

🌳 8 · Minimum spanning tree

"Take the cheapest edge that doesn't make a cycle. Repeat."

That's Kruskal: sort the edges, then use Union-Find to skip any edge that joins two nodes already connected. A tree on n nodes has n − 1 edges, so edgesUsed === n - 1 means everything is connected. You can break there to skip the remaining edges.

// 🌳 MIN COST TO CONNECT ALL POINTS (Kruskal + Union-Find)
function minCostConnectPoints(points: number[][]): number {
    const n = points.length;
    const parent = Array.from({length: n}, (_, i) => i);
    const rank = Array(n).fill(0);

    function find(x: number): number {
        let root = x;

        while(parent[root] !== root) {
            root = parent[root];
        }

        while(parent[x] !== root) {
            const next = parent[x];
            parent[x] = root;
            x = next;
        }

        return root;
    }

    function union(x: number, y: number): boolean {
        const px = find(x);
        const py = find(y);

        if(px === py) return false;

        if(rank[px] < rank[py]) parent[px] = py;
        else if(rank[px] > rank[py]) parent[py] = px;
        else {
            parent[px] = py;
            rank[py]++;
        }

        return true;
    }

    const edges: number[][] = []; // [i, j, cost]

    for(let i = 0; i < n; i++) {
        for(let j = i + 1; j < n; j++) {
            const [xi, yi] = points[i];
            const [xj, yj] = points[j];

            const cost = Math.abs(xi - xj) + Math.abs(yi - yj);
            edges.push([i, j, cost]);
        }
    }

    edges.sort((a, b) => a[2] - b[2]);
    const eLen = edges.length;
    let edgesUsed = 0;
    let totalCost = 0;

    for(let i = 0; i < eLen; i++) {
        const [u, v, w] = edges[i];

        if(union(u, v)) { // joins two groups → keep the edge
            edgesUsed++;
            totalCost += w;
        }
    }

    return edgesUsed === n - 1 ? totalCost : -1; // -1 if graph can't be fully connected
};

• Prim grows one tree from a node, always taking the cheapest edge leaving it. It's Dijkstra's code with w in place of d + w. On 1584 (every pair is an edge) an array-based Prim is O(n²) and beats sorting n² edges.
• 1168🔒 Optimize Water Distribution: add a fake node 0 and give each house an edge to it costing its well price. Now it's a plain MST.

🚀 9 · Stretch topics L5 / HARD

Know these if you have time. They show up in harder rounds, rarely in a typical L3/L4 loop.

Use every edge once: Hierholzer

🧳 Use every ticket exactly once. Walk until you're stuck; the place you get stuck is where the trip ends, so write it down last-to-first.

// 🛫 RECONSTRUCT ITINERARY (Hierholzer, post-order)
function findItinerary(tickets: string[][]): string[] {
    const graph = new Map<string, string[]>();
    const res: string[] = [];

    for(const [u, v] of tickets) {
        if(!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push(v);
    }

    for(const values of graph.values()) {
        values.sort().reverse(); // pop() then gives the smallest
    }

    function dfs(node: string) {
        const nei = graph.get(node) ?? [];

        while(nei.length > 0) {
            const nextNode = nei.pop()!; // use each ticket once
            dfs(nextNode);
        }

        res.push(node); // post-order: add only after every ticket is used
    }

    dfs('JFK');
    return res.reverse();
};

Visiting every edge once (Euler) is O(E). Visiting every node once (Hamiltonian) is NP-hard, so don't try to code it. In a directed graph, a path exists if every node has in = out, except possibly one start (out = in + 1) and one end.

Bridges: critical connections

🌉 A bridge is the only road to an island: remove it and the graph splits. An edge is safe when the far side has another way back (a back edge) to above it.

// 🌉 CRITICAL CONNECTIONS (bridges, disc/low)
function criticalConnections(n: number, connections: number[][]): number[][] {
    const graph: number[][] = Array.from({length: n}, () => []);

    for(const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }

    // disc[node] = arrival timestamp, FIXED once set
    const disc: number[] = Array(n).fill(-1);
    // low[node] = earliest timestamp reachable from the node's subtree via a back edge
    const low: number[] = Array(n).fill(-1);

    const bridges: number[][] = [];
    let timer = 0;

    function dfs(node: number, par: number): void {
        disc[node] = low[node] = timer++;

        for(const nei of graph[node]) {
            if(nei === par) continue; // skip the edge we just walked in on

            if(disc[nei] === -1) {
                dfs(nei, node);
                low[node] = Math.min(low[node], low[nei]); // nei's low is final now
                if(low[nei] > disc[node]) { // nei cannot reach back above node
                    bridges.push([node, nei]);
                }
            } else {
                low[node] = Math.min(low[node], disc[nei]); // back edge: use disc[nei]
            }
        }
    }

    dfs(0, -1);

    return bridges;
};

Articulation points (critical nodes) use the same code with low[next] >= disc[node], plus a rule that the DFS root counts only if it has 2 or more children.

Visit all nodes: BFS over (node, bitmask)

🎒 The node alone isn't enough: being at B having seen {A} is a different situation from being at B having seen {A, C}. So the BFS state is (node, set of visited nodes), and with n ≤ 12 that set fits in a bitmask.

// 🧭 SHORTEST PATH VISITING ALL NODES (BFS over node + bitmask)
function shortestPathLength(graph: number[][]): number {
    const n = graph.length;

    const target = (1 << n) - 1; // every bit set = every node visited
    const visited = Array.from({length: n}, () => Array(target + 1).fill(false));
    const queue: number[][] = [];

    for(let i = 0; i < n; i++) { // may start anywhere
        const mask = 1 << i;
        visited[i][mask] = true;
        queue.push([i, mask]);
    }

    let front = 0;
    let count = 0;

    while(front < queue.length) {
        let size = queue.length - front;

        while(size--) {
            const [node, mask] = queue[front++];

            if(mask === target) return count;

            for(const nei of graph[node]) {
                const neiMask = 1 << nei;
                const nextMask = mask | neiMask;

                if(!visited[nei][nextMask]) {
                    visited[nei][nextMask] = true;
                    queue.push([nei, nextMask]);
                }
            }
        }

        count++;
    }

    return -1;
};

Name-drop only

⭐ 10 · The must-know 20

If you can explain the trick for each in one sentence, you're ready.

⚠️ 11 · Traps

Complexity

Implicit graphs: V = the number of possible states (e.g. rows × cols × k for 1293), E = V × moves per state.

✅ 12 · Self-check

Cover the right column (it's blurred; hover or tap to reveal). Say the answer out loud first.

Write these cold (no peeking)

• DFS 200 Number of Islands
• BFS 994 Rotting Oranges
• Topo 210 Course Schedule II
• Union-Find find + union + 684
• Dijkstra the heap + 743 (LeetCode has MinPriorityQueue; in an interview doc you write the heap yourself, see §2)

Time yourself: each one should take under 10 minutes, heap included.